[c++] BOJ 1417๋ฒˆ :: ๊ตญํšŒ์˜์› ์„ ๊ฑฐ
Algorithm ๋ฌธ์ œ/BOJ 2020. 4. 10. 15:54

๊ตญํšŒ์˜์› ์„ ๊ฑฐ ๋ฌธ์ œ ๋‹ค์†œ์ด๋Š” ์‚ฌ๋žŒ์˜ ๋งˆ์Œ์„ ์ฝ์„ ์ˆ˜ ์žˆ๋Š” ๊ธฐ๊ณ„๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ์ด ๊ธฐ๊ณ„๋ฅผ ์ด์šฉํ•ด์„œ 2008๋…„ 4์›” 9์ผ ๊ตญํšŒ์˜์› ์„ ๊ฑฐ๋ฅผ ์กฐ์ž‘ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋‹ค์†œ์ด์˜ ๊ธฐ๊ณ„๋Š” ๊ฐ ์‚ฌ๋žŒ๋“ค์ด ๋ˆ„๊ตฌ๋ฅผ ์ฐ์„ ์ง€ ๋ฏธ๋ฆฌ ์ฝ์„ ์ˆ˜ ์žˆ๋‹ค. ์–ด๋–ค ์‚ฌ๋žŒ์ด ๋ˆ„๊ตฌ๋ฅผ ์ฐ์„ ์ง€ ์ •ํ–ˆ์œผ๋ฉด, ๋ฐ˜๋“œ์‹œ ์„ ๊ฑฐ๋•Œ ๊ทธ ์‚ฌ๋žŒ์„ ์ฐ๋Š”๋‹ค. ํ˜„์žฌ ํ˜•ํƒ๊ตฌ์— ๋‚˜์˜จ ๊ตญํšŒ์˜์› ํ›„๋ณด๋Š” N๋ช…์ด๋‹ค. ๋‹ค์†œ์ด๋Š” ์ด ๊ธฐ๊ณ„๋ฅผ ์ด์šฉํ•ด์„œ ๊ทธ ๋งˆ์„์˜ ์ฃผ๋ฏผ M๋ช…์˜ ๋งˆ์Œ์„ ๋ชจ๋‘ ์ฝ์—ˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ๊ธฐํ˜ธ 1๋ฒˆ์ด๋‹ค. ๋‹ค์†œ์ด๋Š” ์‚ฌ๋žŒ๋“ค์˜ ๋งˆ์Œ์„ ์ฝ์–ด์„œ ์ž์‹ ์„ ์ฐ์ง€ ์•Š์œผ๋ ค๋Š” ์‚ฌ๋žŒ์„ ๋ˆ์œผ๋กœ ๋งค์ˆ˜ํ•ด์„œ ๊ตญํšŒ์˜์›์— ๋‹น์„ ์ด ๋˜๊ฒŒ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋‹ค๋ฅธ ๋ชจ๋“  ์‚ฌ๋žŒ์˜ ๋“ํ‘œ์ˆ˜ ๋ณด๋‹ค ๋งŽ์€ ๋“ํ‘œ์ˆ˜๋ฅผ ๊ฐ€์งˆ ๋•Œ, ๊ทธ ์‚ฌ๋žŒ์ด ๊ตญํšŒ์˜์›์— ๋‹น์„ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด์„œ, ๋งˆ์Œ์„ ์ฝ์€ ๊ฒฐ๊ณผ ๊ธฐํ˜ธ 1๋ฒˆ์ด 5ํ‘œ, ๊ธฐํ˜ธ 2๋ฒˆ์ด..