https://www.acmicpc.net/problem/1149
풀이
1번 집부터 N번 집까지 있을 때 인접한 두 집의 색이 같지 않아야 하는 규칙을 만족하는 비용의 최솟값을 구하는 문제다. Dynamic Programming을 이용해 해결할 수 있다.
각 인접한 집의 색은 겹치지 않아야 하므로 현재 집의 색을 저장하는 자료구조가 필요하다. 따라서 dp table을 2차원으로 초기화하며 dp[i][j]는 다음과 같다.
// j==0 빨강, j==1 초록, j==2 파랑
dp[i][j] = i번째 집일 때 j번째 색을 사용할 때의 최소 비용즉 min(dp[n])이 조건에 만족하는 N번째 집의 색을 칠하는 최소비용이다.
같은 색의 집이 연달아 나올 수 없으므로 dp[i][j]의 갱신은 다음과 같다.
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + houses[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + houses[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + houses[i][2]코드
# Initial
answer = 0 # 모든 집을 칠하는 비용의 최솟값
N = int(input())
houses = [[0 for _ in range(3)] for _ in range(N)] # 빨강, 초록, 파랑
for i in range(N):
houses[i] = list(map(int, input().split()))
# Make dp table
# dp[i][0] = i번째 에서 빨강을 사용할 때 비용
# dp[i][1] = i번째 에서 초록을 사용할 때 비용
# dp[i][2] = i번째 에서 파랑을 사용할 때 비용
dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(N):
if i == 0:
dp[i][0] = houses[i][0]
dp[i][1] = houses[i][1]
dp[i][2] = houses[i][2]
else:
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + houses[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + houses[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + houses[i][2]
# Answer
answer = min(dp[N - 1])
print(answer)
:)