[백준] 자바 Java, 1149번: 동적계획법 > RGB거리

 

1149번: RGB거리

---

문제

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보다 작거나 같은 자연수이다.

 

출력

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

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

나의 풀이

• Top-down 방식 사용

dp[][] 테이블

dp[][] 테이블을 아래와 같이 생성 후 n-1인 재귀하면서 더 안쪽의 값을 계산+누적

package level15_dynamicProgramming;

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

// 백준 1149번 문제] RGB거리
public class Baekjoon1149 {
    public static int n; // 집의 개수
    public static int[][] arr; // 각 집의 페인팅 비용
    public static  int[][] dp; // 누적합 저장 배열


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

        n = Integer.parseInt(br.readLine()); // 집의 개수
        arr = new int[n][3]; // 각 집의 페인팅 비용
        dp = new int[n][3]; // 누적합 저장 배열

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 입력 end

        // dp[][] 초기화
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][2];

        System.out.println(Math.min(Math.min(dp(n-1, 0), dp(n-1, 1)), dp(n-1, 2)));

    } //main end

    public static int dp(int n, int color) { // 위치, 컬러
        if(dp[n][color] == 0) { // 계산한 누적합이 없을 경우
            // 색상에 따라서 이전 집의 다른색상을 재귀 호출하여 더 작은 값과 현재의 집의 비용을 더해서 저장
            if(color == 0) {
                dp[n][color] = arr[n][color] + Math.min(dp(n-1, 1), dp(n-1, 2)); // 현재 위치의 비용과 이전 집의 누접값을 더함!
            } else if(color == 1) {
                dp[n][color] = arr[n][color] + Math.min(dp(n-1, 0), dp(n-1, 2));
            } else {
                dp[n][color] = arr[n][color] + Math.min(dp(n-1, 0), dp(n-1, 1));
            }
        }
        return dp[n][color];
    }

}

 

결과