[ 백준 1149번 JAVA ] RGB 거리

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

1149번: RGB거리

 

동적 계획법

복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법. 

메모리제이션을 사용한다. 메모리제이션이란 부분 문제를 풀었을때, DP 테이블에 해당 문제를 저장해놓고, 다음에 같은 문제가 나왔을때, 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다. 

 

review

이번 문제는 N개의 집을 입력받고, N개의 집부터 n-1, n-2로 배열을 파고들면서 최소비용을 가질 수 있는 값을 dp배열에 row = 1 부터 저장을 하게 된다. 이러한 재귀에서 중복된 계산이 일어나지 않도록 다음과 같은 조건을 걸어 메모리제이션 되도록 한다. 

if(dp[r][color]==0)

 

Solution

package Algo_스터디.Fev_4주차;

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

public class RGB거리 {
    static int[][] dp, cost;
    static int N;
    public static void main(String[] args) throws IOException {
        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        cost = new int[N+1][3];

        for(int i=1 ; i<=N;  i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++){
                cost[i][j]= Integer.parseInt(st.nextToken());
            }
        }// 입력받기 완료

        dp = new int[N+1][3];
        for(int i=0; i<3; i++) calcost(N,i);
        System.out.println(Math.min(dp[N][0],Math.min(dp[N][1],dp[N][2])));
    }
    public static int calcost(int r, int color){
        if(r==1) return cost[r][color];

        if(dp[r][color]==0) {// 탐색하지 않은 배열일 경우.
            if (color == 0) {
                dp[r][color] = cost[r][color] + Math.min(calcost(r - 1, 1), calcost(r - 1, 2));
            } else if (color == 1) {
                dp[r][color] = cost[r][color] + Math.min(calcost(r - 1, 0), calcost(r - 1, 2));
            } else {
                dp[r][color] = cost[r][color] + Math.min(calcost(r - 1, 0), calcost(r - 1, 1));
            }
        }
        return dp[r][color];
    }
}