[백준][17404번] RGB거리 2

문제 URL

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

전체 풀이

1) D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값이다.

• j=0 -> 빨강
• j=1 -> 초록
• j=2 -> 파랑

2) 하지만, 1번과 N번 집이 같은 색이 되지 않아야한다. 1번 집과 n번 집의 색은 다음 6가지가 가능하다.

1번집 색을 빨강으로 고정하고 답을 구하면, 다음 6가지 중 2가지를 구할수있다.

• 빨강, 초록
• 빨강, 파랑 1번집 색을 초록으로 고정하고 답을 구하면, 다음 6가지 중 2가지를 구할수있다.
• 초록, 빨강
• 초록, 파랑 1번집 색을 파랑으로 고정하고 답을 구하면, 다음 6가지 중 2가지를 구할수있다.
• 파랑, 빨강
• 파랑, 초록

즉, 1번집의 색상을 미리 정해놓은 다음 dp를 3번 수행해서 정답을 구할 수 있다.

나의 풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static int MAX = 1001;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] m = new int[n][3];
        int[][] d = new int[n][3];

        //input
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                m[i][j] = sc.nextInt();
            }
        }


        int ans = Integer.MAX_VALUE;
        // 첫번째집 색상, 마지막집 색상을 지정한후 나머지 연산(가운데의 최소비용계산) 진행한다.
        //첫번째집 색상
        for (int i = 0; i < 3; i++) {
            //마지막집 색상
            for (int j = 0; j < 3; j++) {
                if (i == j) continue;
                init(d);
                d[0][i] = m[0][i];

                for (int x = 1; x <= n - 1; x++) {
                    for (int y = 0; y < 3; y++) {
                        d[x][y] = Math.min(d[x - 1][(y + 1) % 3] + m[x][y], d[x - 1][(y + 2) % 3] + m[x][y]);
                    }
                }

                ans = Math.min(ans, d[n - 1][j]);
            }
        }

        System.out.println(ans);
    }

    public static void init(int[][] d) {
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < 3; j++) {
                d[i][j] = MAX;
            }
        }
    }
}

비슷한 풀이

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n+1][3];
        int[][] d = new int[n+1][3];
        for (int i=1; i<=n; i++) {
            for (int j=0; j<3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int ans = 1000*1000 + 1;
        for (int k=0; k<=2; k++) { // house1's color
            for (int j=0; j<=2; j++) {
                if (j == k) {
                    d[1][j] = a[1][j];
                } else {
                    d[1][j] = 1000*1000+1;
                }
            }
            for (int i=2; i<=n; i++) {
                d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + a[i][0];
                d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + a[i][1];
                d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + a[i][2];
            }
            for (int j=0; j<=2; j++) {
                if (j == k) continue;
                ans = Math.min(ans, d[n][j]);
            }
        }
        System.out.println(ans);
    }
}