E D R , A S I H C RSS
ZeroWiki

How Many Zeros And Digits

AboutHowManyZerosAndDigits

이 λ¬Έμ œλŠ” 주어진 수 μ²΄κ³„μ˜ νŒ©ν† λ¦¬μ–Ό 수의 0의 κ°œμˆ˜μ™€ 숫자의 개수λ₯Ό μ°ΎλŠ” 것이닀. bμ§„μˆ˜ μ²΄κ³„λŠ” 0 ~ b-1 λ²”μœ„μ˜ 숫자λ₯Ό κ°–κ²Œ λœλ‹€.

10μ§„μˆ˜ Nκ³Ό 10μ§„μˆ˜ Bκ°€ ν•œ 쀄씩 μž…λ ₯λœλ‹€. 이 λ•Œ N은 20λΉ„νŠΈμ˜ λΆ€ν˜Έ μ—†λŠ” 숫자이며, μ§„μˆ˜ 체계인 B의 λ²”μœ„λŠ” 1 < B <= 800 이닀. 10μ§„μˆ˜μ—μ„œ 5! = 120 μΌλ•Œ, 16μ§„μˆ˜ μ²΄κ³„μ—μ„œλŠ” 78이 λœλ‹€. κ·Έλž˜μ„œ 16μ§„μˆ˜ 5!은 0이 μ—†λ‹€.

μž…λ ₯에 λŒ€ν•΄μ„œ 주어진 μ§„μˆ˜ μ²΄κ³„μ—μ„œ νŒ©ν† λ¦¬μ–Ό 수의 0의 κ°œμˆ˜μ™€ 숫자의 개수λ₯Ό ν•œ 쀄씩 좜λ ₯ν•œλ‹€. 두 숫자 μ‚¬μ΄μ—λŠ” 곡백으둜 κ΅¬λΆ„ν•œλ‹€. 0의 κ°œμˆ˜μ™€ 숫자의 κ°œμˆ˜κ°€ 2^31-1보닀 ν¬μ§€λŠ” λͺ»ν•  것이닀.

Input 

~cpp 
2 10
5 16
5 10

Output 

~cpp 
0 1
0 2
1 3

풀이

μž‘μ„±μž μ‚¬μš©μ–Έμ–΄ κ°œλ°œμ‹œκ°„ μ½”λ“œ
문보창 C++ ? HowManyZerosAndDigits/문보창
μž„μΈνƒ Java ? HowManyZerosAndDigits/μž„μΈνƒ
주의 : 일단 10진법 μ΄μƒμ˜ 진법도 10μ§„μˆ˜λ‘œ ν‘œν˜„ν•œλ‹€κ³  κ°€μ •ν•˜κ³  문제λ₯Ό ν’€μ—ˆμŒ
(예λ₯Ό λ“€μ–΄ A0 λŒ€μ‹  10 0 이라고 ν‘œν˜„ν•œλ‹€κ³  κ°€μ •)
κΉ€νšŒμ˜ C++ ? HowManyZerosAndDigits/κΉ€νšŒμ˜
ν—ˆμ•„μ˜ C++ 1μ‹œκ°„ 30λΆ„ HowManyZerosAndDigits/ν—ˆμ•„μ˜

μ“°λ ˆλ“œ

λ§Œμ•½ 800진법일 경우 0~9 κΉŒμ§€μ˜ μˆ«μžλŠ” ν‘œν˜„ν• μˆ˜ μžˆκ² μ§€λ§Œ κ·Έ μ΄ν›„μ˜ μˆ«μžλŠ” μ–΄λ–»κ²Œ ν‘œν˜„ν•˜λ‚˜μš”? 16μ§„λ²•μœΌλ‘œ λ‚˜νƒ€λ‚Όλ•Œ 0μ—μ„œ F 둜 ν‘œν˜„ν•˜λŠ” κ²ƒμ²˜λŸΌ, 800μ§„λ²•μ—μ„œ 10μ΄μƒμ˜ 수λ₯Ό ν‘œν˜„ν•΄μ•Ό ν•  방법이 μžˆμ–΄μ•Ό ν•  것 κ°™μ€λ°μš”. μ•ŒνŒŒλ²³μ„ μ΄μš©ν•œλ‹€κ³  해도 Z(35)μ΄ν›„μ˜ μˆ˜λŠ” ν‘œν˜„ν•  방법이 μ—†λŠ”λ°μš”. 이에 λŒ€ν•œ μ •μ˜κ°€ μ—†λ‹€λ©΄ μ •ν™•ν•œ 닡을 ꡬ할 수 없을 것 κ°™μŠ΅λ‹ˆλ‹€(λ¬Έμ œμ—μ„œ λ§ν•œ 0의 개수말이죠). κ°„λ‹¨ν•œ 예λ₯Ό λ“€μ–΄ μ„€λͺ…ν•˜μžλ©΄,
{{|
16μ§„μˆ˜ 0xA0 μ—μ„œ λ‘λ²ˆμ§Έ 자리의 Aλ₯Ό κ·Έλƒ₯ A둜 받아듀이면 0의 κ°œμˆ˜λŠ” 1κ°œμ΄κ² μ§€λ§Œ, AλΌλŠ” ν‘œκΈ° λŒ€μ‹ μ— 10이라고 ν‘œκΈ°ν–ˆμœΌλ©΄ 0의 κ°œμˆ˜λŠ” 2μ΄μ§€μš”. κ²Œλ‹€κ°€ μ΄λ•Œμ—λŠ” 전체 숫자의 개수λ₯Ό 2라고 ν•΄μ•Ό ν•˜λŠ”μ§€ 3이라고 ν•΄μ•Ό ν•˜λŠ”μ§€λ„ λͺ…ν™•ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€. λ§Œμ•½ λ¬Έμ œμ—μ„œ 숫자의 κ°œμˆ˜λΌλŠ” ν‘œν˜„ λŒ€μ‹ μ— 자리수라고 ν‘œν˜„ν–ˆμœΌλ©΄ 2μ΄κ² μ§€λ§Œ λ¬Έμ œμ—μ„œ 숫자의 개수라고 ν–ˆμœΌλ‹ˆ 문제λ₯Ό μ΄ν•΄ν•˜λŠ”λ° 어렀움이 λ§ŽμŠ΅λ‹ˆλ‹€. 또 10μ§„μˆ˜ 680000 을 800μ§„μˆ˜λ‘œ λ³€ν™˜ν• λ•Œ 이λ₯Ό μ–΄λ–»κ²Œ ν‘œκΈ°ν•΄μ•Ό 할지도 λͺ…ν™•ν•˜μ§€κ°€ μ•ŠμŠ΅λ‹ˆλ‹€.
|}}
그리고 문제λ₯Ό μ„€λͺ…ν•˜λŠ” λ¬Έμž₯의 λ‚΄μš©μ΄ ν•œλ²ˆμ— 와 닿지가 μ•Šλ„€μš”. λ¬Έμž₯을 쑰금 닀듬어 μ£Όμ‹œλ©΄ κ°μ‚¬ν•˜κ² μŠ΅λ‹ˆλ‹€. ^^ - μž„μΈνƒ

책에 μžˆλŠ” μ˜¬λ¦Όν”Όμ•„λ“œ 문제 원문 κ·ΈλŒ€λ‘œλ₯Ό μ‹€μ—ˆμŠ΅λ‹ˆλ‹€. λ¬Έμ œκ°€ λͺ…ν™•ν•˜μ§€ μ•Šλ‹€λŠ” 점을 λΆ€μ •ν•  순 μ—†μ§€λ§Œ, λ¬Έμ œμ— 손을 댈 경우 제 주관적인 생각이 문제의 틀을 바꿔버릴 수 μžˆκΈ°λ•Œλ¬Έμ— μ–΄μ©”μˆ˜ μ—†μŠ΅λ‹ˆλ‹€. 개인적 μ†Œκ²¬μœΌλ‘œλŠ” N!을 Bμ§„λ²•μœΌλ‘œ λ³€ν™˜ν•˜λŠ” κ²ƒμ΄λ―€λ‘œ, μž…λ ₯을 λ°›λŠ” N이 쑰금만 컀져도 N!이 ꡉμž₯히 컀지기 λ•Œλ¬Έμ— N은 B보닀 μž‘μ€ λ²”μœ„, 즉 Bμ§„μˆ˜ μ²΄κ³„μ—μ„œ ν•œμžλ¦¬λ₯Ό μž…λ ₯λ°›λŠ” λ¬Έμ œκ°€ μ•„λ‹κΉŒ ν•©λ‹ˆλ‹€. λ˜ν•œ, 문제의 λ§ˆμ§€λ§‰ 쑰건인 2^31-1 같이 intν˜•μ˜ μ˜€λ²„ν”Œλ‘œμš°λ°©μ§€λ₯Ό ν•΄ 놓은 κ²ƒμ—μ„œ 보듯 λ²”μœ„λ₯Ό μ–΄λŠμ •λ„ μ œν•œν•΄ λ†“μ•˜λ‹€κ³  λ³΄μ—¬μ§‘λ‹ˆλ‹€. μ •ν™•ν•œ 닡변을 λ“œλ¦¬μ§€ λͺ»ν•΄ μ£„μ†‘ν•©λ‹ˆλ‹€. - 문보창
----
λ¬Έμ œλΆ„λ₯˜
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:25
Processing time 0.0181 sec