[c++] BOJ 20040 :: ์‚ฌ์ดํด ๊ฒŒ์ž„
Algorithm ๋ฌธ์ œ/BOJ 2021. 10. 10. 11:09

๋ฌธ์ œ [์‚ฌ์ดํด ๊ฒŒ์ž„ ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ] 20040๋ฒˆ: ์‚ฌ์ดํด ๊ฒŒ์ž„ ์‚ฌ์ดํด ๊ฒŒ์ž„์€ ๋‘ ๋ช…์˜ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ฐจ๋ก€๋Œ€๋กœ ๋Œ์•„๊ฐ€๋ฉฐ ์ง„ํ–‰ํ•˜๋Š” ๊ฒŒ์ž„์œผ๋กœ, ์„  ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ํ™€์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ, ํ›„ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ง์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ ์ง„ํ–‰ํ•œ๋‹ค. ๊ฒŒ์ž„ ์‹œ์ž‘ ์‹œ 0 ๋ถ€ํ„ฐ n − 1 ๊นŒ์ง€ ๊ณ ์œ ํ•œ www.acmicpc.net ์‚ฌ์ดํด ๊ฒŒ์ž„์€ ๋‘ ๋ช…์˜ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ฐจ๋ก€๋Œ€๋กœ ๋Œ์•„๊ฐ€๋ฉฐ ์ง„ํ–‰ํ•˜๋Š” ๊ฒŒ์ž„์œผ๋กœ, ์„  ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ํ™€์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ, ํ›„ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ง์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ ์ง„ํ–‰ํ•œ๋‹ค. ๊ฒŒ์ž„ ์‹œ์ž‘ ์‹œ 0 ๋ถ€ํ„ฐ n − 1 ๊นŒ์ง€ ๊ณ ์œ ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ€์—ฌ๋œ ํ‰๋ฉด ์ƒ์˜ ์  n ๊ฐœ๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ์ค‘ ์–ด๋Š ์„ธ ์ ๋„ ์ผ์ง์„  ์œ„์— ๋†“์ด์ง€ ์•Š๋Š”๋‹ค. ๋งค ์ฐจ๋ก€ ๋งˆ๋‹ค ํ”Œ๋ ˆ์ด์–ด๋Š” ๋‘ ์ ์„ ์„ ํƒํ•ด์„œ ์ด๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„ ๋ถ„์„ ๊ธ‹๋Š”๋ฐ, ์ด์ „์— ๊ทธ๋ฆฐ ์„ ๋ถ„์„ ๋‹ค์‹œ ๊ทธ์„ ์ˆ˜๋Š” ์—†์ง€๋งŒ ์ด๋ฏธ ๊ทธ๋ฆฐ ๋‹ค๋ฅธ ..