RGB거리 1149

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

어떻게 풀어야 할지 몰라서 풀이를 보다가 힌트를 얻고 풀었다

https://www.acmicpc.net/problem/2579
문제와 거의 같은 방식으로 풀 수 있다

DP를 이차원 배열로 만들고 하나의 행에 3개의 열로 구성한다 RGB가 3개니까.
입력받은 첫번째 행은 그냥 DP 에 넣으면 된다 그다음 두번째 입력부터는
하나의 행에서 RGB 마다 이전행에서 선택가능한 경우중 작은것을 선택해서 DP에 넣는 방식이다

그림으로 그려보면 다음과 같다

O(N)

import java.io.*;
public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String[] input;

        int[][] dp = new int[N][3];
        input = br.readLine().split(" ");
        for (int i = 0; i < 3; i++) {

            dp[0][i] = Integer.parseInt(input[i]);
        }

        for (int i = 1; i < N; i++)
        {
            input = br.readLine().split(" ");

            int R = Integer.parseInt(input[0]);
            int G = Integer.parseInt(input[1]);
            int B = Integer.parseInt(input[2]);

            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + R;
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + G;
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + B;
        }

        System.out.println(Math.min(Math.min(dp[N-1][0], dp[N-1][1]), dp[N-1][2]));
    }
}