[python]๋ฐฑ์ค€ 17827๋ฒˆ: ๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ
Algorithm ๋ฌธ์ œ/BOJ 2020. 3. 13. 14:41

๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ ์‹œ๊ฐ„ ์ œํ•œ ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ ์ œ์ถœ ์ •๋‹ต ๋งž์€ ์‚ฌ๋žŒ ์ •๋‹ต ๋น„์œจ 1 ์ดˆ 256 MB 597 219 175 40.984% ๋ฌธ์ œ ์˜์ง„์ด๋Š” ๋‹ฌํŒฝ์ด๋ฅผ ์ข‹์•„ํ•œ๋‹ค. ๋‹ฌํŒฝ์ด๋ฅผ ๋„ˆ๋ฌด๋„ˆ๋ฌด ์ข‹์•„ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํŠน์ •ํ•œ ๋ชจ์–‘์˜ ๋‹จ๋ฐฉํ–ฅ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์— ๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ๋ผ๋Š” ์ด๋ฆ„์„ ๋ถ™์—ฌ์ฃผ์—ˆ๋‹ค. ์ผ๋ฐ˜์ ์ธ ์„ ํ˜• ๋‹จ๋ฐฉํ–ฅ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์˜ ๊ฐ ๋…ธ๋“œ ๋ฒˆํ˜ธ๋ฅผ ์—ฐ๊ฒฐ๋œ ์ˆœ์„œ๋Œ€๋กœ 1, 2, ..., N์ด๋ผ ํ•˜์ž. ์ด๋•Œ N๋ฒˆ ๋…ธ๋“œ๋Š” ์•„๋ฌด ๋…ธ๋“œ๋„ ๊ฐ€๋ฆฌํ‚ค์ง€ ์•Š๋Š”๋ฐ, ์—ฌ๊ธฐ์„œ N๋ฒˆ ๋…ธ๋“œ๊ฐ€ 1๋ฒˆ ๋…ธ๋“œ๋ฅผ ์ œ์™ธํ•œ ์ž„์˜์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌ์ผœ ์‚ฌ์ดํด์„ ์ด๋ฃจ๊ฒŒ ๋˜๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ๋ผ๊ณ  ํ•œ๋‹ค. ๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ๋Š” ๊ฐ ๋…ธ๋“œ๋‹น ํ•˜๋‚˜์˜ ์ •์ˆ˜๋ฅผ ์ €์žฅํ•œ๋‹ค. ์ฆ‰, ๋‹ฌํŒฝ์ด ๋ฆฌ์ŠคํŠธ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ƒ๊ธด ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์ด๋‹ค. ๋…ธ๋“œ ์•ˆ์˜ ์ˆ˜๋Š” ์ €์žฅ๋œ ๊ฐ’์„ ๋œปํ•œ๋‹ค. "๋‹ฌํŒฝ์•„ ๋‹ฌํŒฝ์•„ 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ ํ•œ ์นธ์”ฉ..