[BOJ] 2225 : ํฉ๋ถํด
๋ฌธ์ ๋งํฌ 2225๋ฒ: ํฉ๋ถํด (acmicpc.net) 2225๋ฒ: ํฉ๋ถํด ์ฒซ์งธ ์ค์ ๋ต์ 1,000,000,000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค. www.acmicpc.net DP๋ฅผ ์ด์ฉํด์ ์ซ์ N์ K๊ฐ์ ์ซ์ ์กฐํฉ์ผ๋ก ๋ง๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ . ํ์ด DP[N][K] ๋ฐฐ์ด์ ๋ง๋ค์ด์ DP[Y][X] ์๋ ์ซ์ Y๋ฅผ ์ซ์ X๊ฐ๋ฅผ ์กฐํฉํด์ ๋ง๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ ์ฅํด์ผ๊ฒ ๊ตฌ๋ ์๊ฐํ๋ค. ์ผ๋จ Bottom-up ๋ฐฉ์์ผ๋ก DP[0][1], DP[1][1], ... , DP[N][1], DP[0][2], DP[1][2], ... , DP[N][K] ์ด๋ ๊ฒ ์ฑ์๋๊ฐ์ผ๊ฒ ๋ค๊ณ ์๊ฐ์ ํ์ง๋ง, ์ ํ์์ ์ด๋ป๊ฒ ํด์ผํ ์ง๊ฐ ๊ด๊ฑด์ด๋ค. ์ฒ์์๋ ์๋ฅผ ๋ค์ด DP[3][3]์ ์ฑ์ฐ๊ธฐ ์ํด์๋ DP[0][1] * DP[3..
2022. 3. 2.