[python]๋ฐฑ์ค€ 4811๋ฒˆ : ์•Œ์•ฝ
Algorithm ๋ฌธ์ œ/BOJ 2020. 2. 21. 00:23

https://www.acmicpc.net/problem/4811 ๋ฌธ์ œ 70์„ธ ๋ฐ•์ข…์ˆ˜ ํ• ์•„๋ฒ„์ง€๋Š” ๋งค์ผ ๋งค์ผ ์•ฝ ๋ฐ˜์•Œ์„ ๋จน๋Š”๋‹ค. ์†๋…€ ์„ ์˜์ด๋Š” ์ข…์ˆ˜ ํ• ์•„๋ฒ„์ง€์—๊ฒŒ ์•ฝ์ด N๊ฐœ ๋‹ด๊ธด ๋ณ‘์„ ์„ ๋ฌผ๋กœ ์ฃผ์—ˆ๋‹ค. ์ฒซ์งธ ๋‚ ์— ์ข…์ˆ˜๋Š” ๋ณ‘์—์„œ ์•ฝ ํ•˜๋‚˜๋ฅผ ๊บผ๋‚ธ๋‹ค. ๊ทธ ๋‹ค์Œ, ๊ทธ ์•ฝ์„ ๋ฐ˜์œผ๋กœ ์ชผ๊ฐœ์„œ ํ•œ ์กฐ๊ฐ์€ ๋จน๊ณ , ๋‹ค๋ฅธ ์กฐ๊ฐ์€ ๋‹ค์‹œ ๋ณ‘์— ๋„ฃ๋Š”๋‹ค. ๋‹ค์Œ ๋‚ ๋ถ€ํ„ฐ ์ข…์ˆ˜๋Š” ๋ณ‘์—์„œ ์•ฝ์„ ํ•˜๋‚˜ ๊บผ๋‚ธ๋‹ค. (์•ฝ์€ ํ•œ ์กฐ๊ฐ ์ „์ฒด ์ผ ์ˆ˜๋„ ์žˆ๊ณ , ์ชผ๊ฐ  ๋ฐ˜ ์กฐ๊ฐ ์ผ ์ˆ˜๋„ ์žˆ๋‹ค) ๋ฐ˜ ์กฐ๊ฐ์ด๋ผ๋ฉด ๊ทธ ์•ฝ์„ ๋จน๊ณ , ์•„๋‹ˆ๋ผ๋ฉด ๋ฐ˜์„ ์ชผ๊ฐœ์„œ ํ•œ ์กฐ๊ฐ์„ ๋จน๊ณ , ๋‹ค๋ฅธ ์กฐ๊ฐ์€ ๋‹ค์‹œ ๋ณ‘์— ๋„ฃ๋Š”๋‹ค. ์ข…์ˆ˜๋Š” ์†๋…€์—๊ฒŒ ํ•œ ์กฐ๊ฐ์„ ๊บผ๋‚ธ ๋‚ ์—๋Š” W๋ฅผ, ๋ฐ˜ ์กฐ๊ฐ์„ ๊บผ๋‚ธ ๋‚ ์—๋Š” H ๋ณด๋‚ธ๋‹ค. ์†๋…€๋Š” ํ• ์•„๋ฒ„์ง€์—๊ฒŒ ๋ฐ›์€ ๋ฌธ์ž๋ฅผ ์ข…์ด์— ๊ธฐ๋กํ•ด ๋†“๋Š”๋‹ค. ์ด 2N์ผ์ด ์ง€๋‚˜๋ฉด ๊ธธ์ด๊ฐ€ 2N์ธ..