[백준] 1149번 RPG 거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

이 문제의 조건은 3개이지만..
사실은 다 같은 말을 하고 있다.
그 이유는 
예륻들어 집이 3개만 존재한다고 가정해보자.
그러면 1번집은 2집과 색이 달라야 한다는 조건이 만족해야 하므로 1번조건에 만족한다.

근데 이 조건은 n번집이 n-1번의 집이랑 색이 달라야 한다고 했는데 1번 조건과 같은 대답이다.

그러면 3번 조건을 읽어보면 i번을 기준으로 i-1과 i+1은 색상이 달라야 한다고 했다.

여기에 값을 대입해 보면 쉽게 알 수 있다.

2번,은 1번과 색상이 달라야 한다. - 1번 조건

2번,3번과 색상이 달라야 한다. - 2번 조건

아까 전에 2번 조건이 1번조건과 같은 대답임을 증명?했기 때문에 1번조건 = 2번 조건이 된다.

따라서 1=2=3번은 모두 같은 조건임이 확인 되었다.

 

그러면 이 문제는 어떻게 풀어야 할까?

각 집마다 빨강색, 파랑색, 초록색을 칠할 수 있는 값이 주어진다.

26 40 83
49 60 57
13 89 99

각 행은 집을 뜻한다. 지금 예제는 3개의 집이 존재한다.

문제는 가장 최소 값을 구하는것이다.

근데 잘 생각해보면 첫 번째 집은 그것 자체가 최솟값이 된다. 왜냐하면 이것보다 작게 칠할 수 는 없기 때문이다.

첫 번째 집 : 빨강색 => 26
                초록색 => 40
                파랑색 => 83

이제 두 번째 집도 칠하는 방법도 생각해 봐야 한다.

만약, 첫 번째 집이 빨강색이라면 빨강색은 금지가 되며, 다른 색상도 마찬가지다.
이건 첫 번째집의 기준이 아닌 두 번째집을 기준으로 하여도 같다는 건 위에서 증명하였다.

그러면

첫 번째집이 빨간색으로 칠할경우

첫 번째집이 파란색으로 칠할경우

첫 번째집이 초록색으로 칠할경우

이런 식의 경우가 발생이 된다.

 

내가 해결 한 방식은 다음 과 같다.

어차피 첫 번째집은 그 자체로만으로도 최솟값이기 때문에 첫 번째 dp에 첫번째 값들을 모두 집어 넣고...

나머지는 위 식으로 대체한다. 그러면 정답이다.

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int maps[][] = new int[n + 10][n + 10];
        int dp[][] = new int[n + 10][n + 10];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                maps[i][j] = sc.nextInt();
            }
        }

        for (int j = 1; j <= 3; j++) {
            dp[1][j] = maps[1][j];
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= 3; j++) {
                int result = 0;
                if (j == 1) {
                    result = Math.min(dp[i - 1][j + 1], dp[i - 1][j + 2]);
                }
                if (j == 2) {
                    result = Math.min(dp[i - 1][j - 1], dp[i - 1][j+ 1]);
                }
                if (j == 3) {
                    result = Math.min(dp[i - 1][j - 2], dp[i - 1][j - 1]);
                }
                dp[i][j] = result + maps[i][j];
            }
        }

        int min = (int)(1e9);
            for (int j = 1; j <= 3; j++) {
                min = Math.min(min,dp[n][j]);
        }

        System.out.println(min);
    }

 

이렇게 구하면 마지막 n값에는 모든 조건이 최솟값이 정리가 되어 있다.

마지막 집이 빨간색인 경우,
                파란색인 경우.
                초록색인 경우,

가 나오게 된다. 여기서 가장 최솟값을 구하게 되면 모든 집을 칠하는 비용의 최솟값을 구할 수 있게 된다.