[백준] 1149번: RGB거리 - JAVA

🔗 문제 링크

BOJ 1149번: RGB거리

1149번: RGB거리

 

📝 풀이 과정

만약, N번 집의 색이 빨간색이라면, N + 1의 집의 색깔은 초록색이나 파란색으로 칠하는 경우밖에 존재하지 않는다.

다시 말하면 N번 집의 색이 빨간색이라면 N - 1의 집의 색은 초록색이나 파란색이라는 의미가 된다.

 

따라서, i번째에서 가장 적은 비용으로 빨간색을 칠하는 경우는 $dp[i][0] = Min(dp[i-1][1], dp[i-1][2]) + cost[i][0]$가 되고, 다른 색도 같은 방식으로 진행된다.(0 : R, 1 : G, 2 : B)

 

💻 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] cost = new int[N][3];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++)
                cost[i][j] = sc.nextInt();
        }

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

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


    }
}

 

📊 제출 결과