1149 RGB거리

https://www.acmicpc.net/problem/1149

d[i][j]를 집i를 j색으로 칠할 때 집i까지 짓는 총 비용의 최소값이라 하자. 집i를 j색으로 칠했다면 그 이전 집i-1는 j색을 제외한 2가지 색이 올 수 있고 이 중 최소값과 집i를 j색으로 칠하는 비용인 a[i][j]을 더해주면 d[i][j]이 된다.

d[i][j] = min(d[i-1][k])+a[i][j] (0<=k<3, k!=j)

이 문제에서는 d[i][j]값을 구할 때 이전 행의 정보만 필요하므로 굳이 a 배열을 따로 잡을 필요가 없다. 사실 메모리를 더 줄이자면 d[2][3]만 잡고도 풀 수 있다. 정답은 마지막 행의 값들의 최소값이다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,d[1000][3];
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<3;j++)
        scanf("%d",&d[i][j]);
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(j==0) d[i][j]+=min(d[i-1][1],d[i-1][2]);
            else if(j==1) d[i][j]+=min(d[i-1][0],d[i-1][2]);
            else d[i][j]+=min(d[i-1][0],d[i-1][1]);
        }
    }
    printf("%d",min({d[n-1][0],d[n-1][1],d[n-1][2]}));
    return 0;
}