백준 17404 - RGB거리 2 (Java)

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

17404번: RGB거리 2

코드 :

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

public class Main {
    static int[][] arr;
    static int[][] dp;

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

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


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

        int answer = 1001;

        //1번 집이 R
        dp = new int[N + 1][3];
        dp[1][0] = arr[1][0];
        dp[1][1] = dp[1][2] = 1001;
        answer = Math.min(recur(N, 1), recur(N, 2));

        //1번 집이 G
        dp = new int[N + 1][3];
        dp[1][1] = arr[1][1];
        dp[1][2] = dp[1][0] = 1001;
        answer = Math.min(answer, Math.min(recur(N, 0), recur(N, 2)));

        //1번 집이 B
        dp = new int[N + 1][3];
        dp[1][2] = arr[1][2];
        dp[1][0] = dp[1][1] = 1001;
        answer = Math.min(answer, Math.min(recur(N, 0), recur(N, 1)));


        System.out.print(answer);
    }

    public static int recur(int N, int color){
        if(dp[N][color] == 0 ){
            dp[N][color] = Math.min(recur(N - 1,(color + 1) % 3), recur(N - 1, (color + 2) % 3)) + arr[N][color];
        }
        return dp[N][color];
    }
}

풀이 :

https://programming-beard.tistory.com/141

백준 1149번 - RGB거리 (Java)

RGB거리 문제와 원리는 같다. 하지만 1번째 집과 맨 끝 집의 색깔이 같으면 안된다는 조건이 붙는다.

 

1번째 집이 특정 색깔로 선택되도록 강제하여 dp값을 구하면 된다. 비용의 범위가 1000이하길래 선택될 값 이외에는 1001(Math.min에서 절대로 선택되지 않는 수)로 설정해서, 1번째 값을 강제한 상태로 dp값을 구했다.

 

1번 R일 때  ->  N번 G or B

2번 G일 때 ->  N번 R or B

3번 B일 떄 ->  N번 R or G

 

 

해당 조건을 해결할 방법을 생각해내지 못해서 다른 블로그를 참고했다.

 

 

 

 

참고 :

https://hongjw1938.tistory.com/77

알고리즘 풀이 - 백준 17404(RGB거리 2, DP)