📝 문제 정보#
🧐 관찰 및 접근#
- 현재 집 $i$번의 색을 선택하기 위해 알아야 하는 정보는 $i-1$번째 집의 색이다.
- 따라서 $\text{DP}[i][j]$를 $i$번째 칠했을 때, 집의 색이 $j$인 경우 (빨, 초, 파)로 정의하면 점화식은 다음과 같다.
- $\text{DP}[i][j] = min_{c \neq j}{\text{DP}[i-1][c] +\text{cost}[i][j]}$
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N;
rep(i, 0, N) rep(j, 0, 3) cin >> cost[i][j];
rep(i, 1, N+1) rep(j, 0, 3) DP[i][j] = 1e18;
rep(i, 0, N) rep(cur, 0, 3) rep(nxt, 0, 3) if(cur != nxt) DP[i+1][nxt] = min(DP[i+1][nxt], DP[i][cur] + cost[i][nxt]);
cout << min({DP[N][0], DP[N][1], DP[N][2]});
}