[c++] BOJ 1253 :: ์ข‹๋‹ค
Algorithm ๋ฌธ์ œ/BOJ 2021. 9. 28. 19:51

๋ฌธ์ œ ์ข‹๋‹ค ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ N๊ฐœ์˜ ์ˆ˜ ์ค‘์—์„œ ์–ด๋–ค ์ˆ˜๊ฐ€ ๋‹ค๋ฅธ ์ˆ˜ ๋‘ ๊ฐœ์˜ ํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๋‹ค๋ฉด ๊ทธ ์ˆ˜๋ฅผ “์ข‹๋‹ค(GOOD)”๊ณ  ํ•œ๋‹ค. N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ๊ทธ ์ค‘์—์„œ ์ข‹์€ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋Š” ๋ช‡ ๊ฐœ์ธ์ง€ ์ถœ๋ ฅํ•˜๋ผ. ์ˆ˜์˜ ์œ„์น˜๊ฐ€ ๋‹ค๋ฅด๋ฉด ๊ฐ’์ด ๊ฐ™์•„๋„ ๋‹ค๋ฅธ ์ˆ˜์ด๋‹ค. ํ’€์ด ์ฒ˜์Œ์— ์ƒ๊ฐํ–ˆ๋˜ ๋ฐฉ๋ฒ•์€ ์ฃผ์–ด์ง„ ์ˆซ์ž๋“ค์„ for๋ฌธ 3์ค‘์œผ๋กœ ๋Œ๋ฉด์„œ ๋‘ ์ˆ˜์˜ ํ•ฉ์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š” ์ง€ ์ฐพ๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ž…๋ ฅ์ด ํฌ์ง€ ์•Š์•„์„œ ๊ฐ€๋Šฅํ•  ๊ฒƒ์ด๋ผ ์ƒ๊ฐํ•˜์˜€๊ณ  ํ•ด๋‹น ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•  ๊ฒฝ์šฐ ์ฐพ์œผ๋ ค๋Š” ์ˆซ์ž๋ณด๋‹ค ์ž‘์€ ์ˆ˜๋“ค๋งŒ ๊ณ ๋ คํ•˜๋ฉด ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•˜์˜€๋‹ค. ํ•˜์ง€๋งŒ ๋ฌธ์ œ์—์„œ ์Œ์ˆ˜๊นŒ์ง€ ๋ฒ”์œ„์— ๋“ค์–ด๊ฐ€๋ฏ€๋กœ target์ด ๋œ ์ˆ˜๋ณด๋‹ค ํฐ ์ˆ˜์— ์Œ์ˆ˜๊ฐ€ ๋”ํ•ด์ ธ์„œ target์ธ ์ˆ˜๋ฅผ ๋งŒ๋“ค ์ˆ˜๋„ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ ์–ด์ฐจํ”ผ ์ž…๋ ฅ์ด 10^3 ๋ฐ–์— ๋˜์ง€ ์•Š์œผ๋‹ˆ ์ฃผ์–ด์ง„ ์ˆซ์ž๋“ค ์ค‘ 2๊ฐœ์”ฉ ๊ณจ๋ผ์„œ..