[c++] BOJ 5430 :: AC
Algorithm ๋ฌธ์ œ/BOJ 2021. 9. 7. 16:29

๋ฌธ์ œ AC ๋ฌธ์ œ ๋ฐ”๋กœ๊ฐ€๊ธฐ ์„ ์˜์ด๋Š” ์ฃผ๋ง์— ํ•  ์ผ์ด ์—†์–ด์„œ ์ƒˆ๋กœ์šด ์–ธ์–ด AC๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค. AC๋Š” ์ •์ˆ˜ ๋ฐฐ์—ด์— ์—ฐ์‚ฐ์„ ํ•˜๊ธฐ ์œ„ํ•ด ๋งŒ๋“  ์–ธ์–ด์ด๋‹ค. ์ด ์–ธ์–ด์—๋Š” ๋‘ ๊ฐ€์ง€ ํ•จ์ˆ˜ R(๋’ค์ง‘๊ธฐ)๊ณผ D(๋ฒ„๋ฆฌ๊ธฐ)๊ฐ€ ์žˆ๋‹ค. ํ•จ์ˆ˜ R์€ ๋ฐฐ์—ด์— ์žˆ๋Š” ์ˆซ์ž์˜ ์ˆœ์„œ๋ฅผ ๋’ค์ง‘๋Š” ํ•จ์ˆ˜์ด๊ณ , D๋Š” ์ฒซ ๋ฒˆ์งธ ์ˆซ์ž๋ฅผ ๋ฒ„๋ฆฌ๋Š” ํ•จ์ˆ˜์ด๋‹ค. ๋ฐฐ์—ด์ด ๋น„์–ด์žˆ๋Š”๋ฐ D๋ฅผ ์‚ฌ์šฉํ•œ ๊ฒฝ์šฐ์—๋Š” ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ํ•จ์ˆ˜๋Š” ์กฐํ•ฉํ•ด์„œ ํ•œ ๋ฒˆ์— ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, "AB"๋Š” A๋ฅผ ์ˆ˜ํ–‰ํ•œ ๋‹ค์Œ์— ๋ฐ”๋กœ ์ด์–ด์„œ B๋ฅผ ์ˆ˜ํ–‰ํ•˜๋Š” ํ•จ์ˆ˜์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, "RDD"๋Š” ๋ฐฐ์—ด์„ ๋’ค์ง‘์€ ๋‹ค์Œ ์ฒ˜์Œ ๋‘ ์ˆซ์ž๋ฅผ ๋ฒ„๋ฆฌ๋Š” ํ•จ์ˆ˜์ด๋‹ค. ๋ฐฐ์—ด์˜ ์ดˆ๊ธฐ๊ฐ’๊ณผ ์ˆ˜ํ–‰ํ•  ํ•จ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ตœ์ข… ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ํ’€์ด ๊ทธ๋ƒฅ ๊ตฌํ˜„ ๋ฌธ์ œ string ํ•จ์ˆ˜๋ฅผ ์ตœ๋Œ€ํ•œ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๊ตฌํ˜„..