[c++] BOJ 1461๋ฒˆ :: ๋„์„œ๊ด€
Algorithm ๋ฌธ์ œ/BOJ 2020. 4. 23. 23:45

๋„์„œ๊ด€ https://www.acmicpc.net/problem/1461 ๋ฌธ์ œ ์„ธ์ค€์ด๋Š” ๋„์„œ๊ด€์—์„œ ์ผํ•œ๋‹ค. ๋„์„œ๊ด€์˜ ๊ฐœ๋ฐฉ์‹œ๊ฐ„์ด ๋๋‚˜์„œ ์„ธ์ค€์ด๋Š” ์‚ฌ๋žŒ๋“ค์ด ๋งˆ๊ตฌ ๋†“์€ ์ฑ…์„ ๋‹ค์‹œ ๊ฐ€์ ธ๋‹ค ๋†“์•„์•ผ ํ•œ๋‹ค. ์„ธ์ค€์ด๋Š” ํ˜„์žฌ 0์— ์žˆ๊ณ , ์‚ฌ๋žŒ๋“ค์ด ๋งˆ๊ตฌ ๋†“์€ ์ฑ…๋„ ์ „๋ถ€ 0์— ์žˆ๋‹ค. ๊ฐ ์ฑ…๋“ค์˜ ์›๋ž˜ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์ฑ…์„ ๋ชจ๋‘ ์ œ์ž๋ฆฌ์— ๋†”๋‘˜ ๋•Œ ๋“œ๋Š” ์ตœ์†Œ ๊ฑธ์Œ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์„ธ์ค€์ด๋Š” ํ•œ ๊ฑธ์Œ์— ์ขŒํ‘œ 1์นธ์”ฉ ๊ฐ€๋ฉฐ, ์ฑ…์˜ ์›๋ž˜ ์œ„์น˜๋Š” ์ •์ˆ˜ ์ขŒํ‘œ์ด๋‹ค. ์ฑ…์„ ๋ชจ๋‘ ์ œ์ž๋ฆฌ์— ๋†”๋‘” ํ›„์—๋Š” ๋‹ค์‹œ 0์œผ๋กœ ๋Œ์•„์˜ฌ ํ•„์š”๋Š” ์—†๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์„ธ์ค€์ด๋Š” ํ•œ ๋ฒˆ์— ์ตœ๋Œ€ M๊ถŒ์˜ ์ฑ…์„ ๋“ค ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ฑ…์˜ ๊ฐœ์ˆ˜ N๊ณผ, ์„ธ์ค€์ด๊ฐ€ ํ•œ ๋ฒˆ์— ๋“ค ์ˆ˜ ์žˆ๋Š” ์ฑ…์˜ ๊ฐœ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ฑ…์˜ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. N์€ ..