[Python] ๋ฐฑ์ค€ 2292 - ๋ฒŒ์ง‘
ยท
Algorithm
๋ฌธ์ œ ์œ„์˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์œก๊ฐํ˜•์œผ๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฒŒ์ง‘์ด ์žˆ๋‹ค. ๊ทธ๋ฆผ์—์„œ ๋ณด๋Š” ๋ฐ”์™€ ๊ฐ™์ด ์ค‘์•™์˜ ๋ฐฉ 1๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์ด์›ƒํ•˜๋Š” ๋ฐฉ์— ๋Œ์•„๊ฐ€๋ฉด์„œ 1์”ฉ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฒˆํ˜ธ๋ฅผ ์ฃผ์†Œ๋กœ ๋งค๊ธธ ์ˆ˜ ์žˆ๋‹ค. ์ˆซ์ž N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋ฒŒ์ง‘์˜ ์ค‘์•™ 1์—์„œ N๋ฒˆ ๋ฐฉ๊นŒ์ง€ ์ตœ์†Œ ๊ฐœ์ˆ˜์˜ ๋ฐฉ์„ ์ง€๋‚˜์„œ ๊ฐˆ ๋•Œ ๋ช‡ ๊ฐœ์˜ ๋ฐฉ์„ ์ง€๋‚˜๊ฐ€๋Š”์ง€(์‹œ์ž‘๊ณผ ๋์„ ํฌํ•จํ•˜์—ฌ)๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค๋ฉด, 13๊นŒ์ง€๋Š” 3๊ฐœ, 58๊นŒ์ง€๋Š” 5๊ฐœ๋ฅผ ์ง€๋‚œ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 1,000,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋ฐฉ๊นŒ์ง€ ์ตœ์†Œ ๊ฐœ์ˆ˜์˜ ๋ฐฉ์„ ์ง€๋‚˜์„œ ๊ฐˆ ๋•Œ ๋ช‡ ๊ฐœ์˜ ๋ฐฉ์„ ์ง€๋‚˜๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋‹ต n = int(input()) res = 1 room = 1 while True: if n == 1: print('1') break..