[백준][1149번] RGB 거리

문제 URL

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

나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());
        // 마지막이 j색인 i번째 집까지의 최소값
        // j의 값은 0 빨강, 1 초록, 2 파랑
        int d[][] = new int[size + 1][3];
        int cost[][] = new int[size + 1][3]; // 칠하는비용 - 0 빨강, 1 초록, 2 파랑


        for (int i = 1; i <= size; i++) {
            StringTokenizer tk = new StringTokenizer(bf.readLine());
            for (int j = 0; j < 3; j++)
                cost[i][j] = Integer.parseInt(tk.nextToken());
        }

        for(int i=0; i<=2; i++)
            d[1][i] = cost[1][i];

        for(int i=2; i<=size; i++){
            for(int j=0; j<3; j++){
                d[i][j] += Math.min(d[i-1][(j+1)%3],d[i-1][(j+2)%3]) + cost[i][j];
            }
        }

        int sum = Math.min(Math.min(d[size][0],d[size][1]),d[size][2]);
        System.out.println(sum);
    }
}

느낀점

동적계획법 을 이용한 문제다.

이전 문제들과 유형이 비슷해 무난하게 풀었다. 이 유형 역시 동적계획법 문제중 연속 적인 것을 처리해야하므로 2차원배열을 사용하였다.

• 시간복잡도 : O(N)