Algorithm/BOJ
2022. 3. 12.
[BOJ] LCS(9251)
[๋ฐฑ์ค(BOJ)] LCS(9251) C++ ๋ฌธ์ : BOJ_9251๋ฒ LCS ๋ฌธ์ ์ค๋ช
DP ์ต๋ 1000 ๊ธ์์ ๋ ๋จ์ด๊ฐ ์ฃผ์ด์ง๊ณ , ๋ ๋จ์ด์์ ๊ณตํต๋ ๋ถ๋ถ ์์ด ์ค ๊ฐ์ฅ ๊ธด ์์ด์ ์ฐพ๋ ๋ฌธ์ ์
๋๋ค. ๋ฌธ์ ์์ฒด๋ ๊ฐ๋จํ์ง๋ง, ์์ ํ์์ ์ด์ฉํ๋ฉด ์๊ฐ ์ด๊ณผ๊ฐ ๋๊ธฐ ๋๋ฌธ์ DP๋ฅผ ํ์ฉํ์ฌ ํด๊ฒฐํด์ผ ํ๋ ๋ฌธ์ ์
๋๋ค. Solution ์ ํ๋ฅผ ์ฐธ๊ณ ํด์ DP ์์ ์ง์ผ ํฉ๋๋ค. ๋ ๋ฌธ์์ด์ ๊ธธ์ด๋งํผ 2์ค for ๋ฌธ์ ์ํํ๋ฉด์ ๋ฌธ์๊ฐ ๊ฐ์ ๋์ ๋ค๋ฅผ ๋ ๋ ์กฐ๊ฑด์ผ๋ก dp ์์ ์ธ์์ค๋๋ค. ๋ ๋ฌธ์์ด์ด ๊ฐ๋ค๋ฉด, dp[i][j] = dp[i-1][j-1]+1 ์ฆ, ์ ํ์์ ๋๊ฐ์ ์ dp ๊ฐ + 1์
๋๋ค. ๋ ๋ฌธ์์ด์ด ๋ค๋ฅด๋ค๋ฉด, dp[i][j] = max(dp[i][j-1], dp[i-1][j]) ์ฆ, ์ ํ์..