์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 3 1

[๋ฐฑ์ค€ / C++] 10989๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 3 ํ’€์ด

๋ฌธ์ œ ์„ค๋ช… https://www.acmicpc.net/problem/10989 10989๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 3 ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 10,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 10,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆซ์ž๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ถœ๋ ฅํ•œ๋‹ค. ๋ฌธ์ œ ํ’€์ด ์‹œ๊ฐ„์ œํ•œ์ด 8์ดˆ์ด๊ณ  ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ์ด 8MB์ธ๋ฐ, ์ตœ๋Œ€ N์˜..