๐ ๋ฌธ์ ํ์ํ๊ธฐ
์ง์ ๊ฐ์ N (2 ≤ N ≤ 1,000)
์ ๋ถ ์์ N๊ฐ์ ์ง์ด 1๋ฒ๋ถํฐ N๋ฒ๊น์ง ์์๋๋ก ์์
๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋ ์ค ํ๋์ ์์ผ๋ก ์น ํด์ผ ํจ
๊ฐ ์ง๋ง๋ค ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์น ํ๋ ๋น์ฉ์ด ๊ฐ๊ฐ ๋ค๋ฆ
๊ฐ ์ง์ ์ด์์ง๊ณผ ์์ด ๊ฐ์ง ์์์ผ ํจ
๋ชจ๋ ์ง์ ์น ํ๋ ๋น์ฉ์ ์ต์๊ฐ ๊ตฌํ๊ธฐ
์๊ณ ๋ฆฌ์ฆ ์ ํํ๊ธฐ
์ด ๋ฌธ์ ์์ ํ์ธํ ์ ์๋ ๋ถ๋ถ์ ๊ฐ ์ง์ ์์น ๋น์ฉ์ ์ด์ ์ง์ ์์น ์ ์ํฅ์ ๋ฐ๋๋ค๋ ๊ฒ์ด๋ค. ์ฆ, i๋ฒ์งธ ์ง์ ์์น ๋น์ฉ์ i+1๋ฒ์งธ ์ง์ ์์น ๋น์ฉ๊ณผ ์ฐ๊ฒฐ๋์ด ์๋ค. i๋ฒ ์งธ ์ง์ ๋นจ๊ฐ์ผ๋ก ์น ํ๋ฉด, i+1๋ฒ์งธ ์ง์ ์ด๋ก ๋๋ ํ๋์ผ ๋์ ์ต์ ๋น์ฉ์ ๊ณ ๋ คํด์ผ ํ๋ค.
๊ฐ ์ง์ ์์น ๋น์ฉ์ ๊ณ์ฐํ๊ณ ์ ์ฅํ์ฌ ๋ค์ ์ง์ ์ต์ ์์น ๋น์ฉ์ ๊ฒฐ์ ํด์ผ ํ๋ฏ๋ก DP๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด ์ ํฉํ๋ค.
์ ํ์ ์ธ์ฐ๊ธฐ
- dp[i][color] -> i๋ฒ์งธ ์ง์ color์(0: ๋นจ๊ฐ, 1:์ด๋ก, 2:ํ๋)์ผ๋ก ์น ํ์ ๋์ 1๋ฒ์งธ๋ถํฐ i๋ฒ์งธ ์ง๊น์ง ์น ํ๋ ์ต์ ๋น์ฉ
- dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + color_cost[i][0]
- dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + color_cost[i][1]
- dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + color_cost[i][2]
๐ ์ฝ๋ ์ค๊ณํ๊ธฐ
1. ์ง์ ๊ฐ์(N) ์ ๋ ฅ ๋ฐ๊ธฐ
2. ๊ฐ ์ง์ ๋นจ๊ฐ, ์ด๋ก, ํ๋์ผ๋ก ์์น ํ ๋์ ๋น์ฉ 2์ฐจ์ ๋ฆฌ์คํธ(color_cost)์ ์ ์ฅํ๊ธฐ
3. 3xN ํฌ๊ธฐ์ ์ด์ฐจ์ dp ๋ฆฌ์คํธ ์์ฑ
4. dp[0]์ color_cost[0]์ ๋ฐ๋ผ ์ด๊ธฐํํ๊ธฐ
5. ์ ํ์์ ๋ฐ๋ผ dp ๋ฆฌ์คํธ ์ฑ์ฐ๊ธฐ
6. min(dp[n-1]) ์ถ๋ ฅํ๊ธฐ
๐ ์ ๋ต์ฝ๋
N = int(input())
color_cost = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
dp[0] = color_cost[0]
for i in range(1, N):
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + color_cost[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + color_cost[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + color_cost[i][2]
print(min(dp[N-1]))
728x90