[실버 1] RGB거리

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

1149번: RGB거리

풀기 전:

그리디는 아닌 것 같다 맨 처음 작은 걸 골랐다고 해도 뒤에 엄청 큰 게 나올 수도 있다

 

그러면 모든 경우를 구할까? 3^1000 이네 안 되겠다

 

그러면 dp [i][j] -> i번째 집 색이 j일 때 최소 값으로 정의하고 구해보자

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N;
        int[][] costs;

        N = Integer.parseInt(br.readLine());
        costs = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            costs[i][0] = Integer.parseInt(st.nextToken());
            costs[i][1] = Integer.parseInt(st.nextToken());
            costs[i][2] = Integer.parseInt(st.nextToken());
        }
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////

무난하게 입력받기

        int[][] dp = new int[N + 1][3];

        for (int i = 1; i <= N; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
        }

        sb.append(Math.min(Math.min(dp[N][0],dp[N][1]),dp[N][2])+" ");
        System.out.println(sb);

    }
}

 

dp [i][0] 은 i-1 집 중에 다른 색 중에 작은 걸 고르고 자신의 value 더하기

dp [N]에서 가장 최솟값을 구한다

 

이게 왜 실버1?