[백준 1149번 : RGB거리] java 풀이

이 문제는 나에게 고통을 줬어..
생각보다 간단한 문제인데 굉장히 헤맸던 거 같다.

처음 풀었던 방법은 이랬다.

• 1번 집에 최소 비용을 가지는 색을 칠한다
• 그 다음 집은 1번 집에 칠한 색을 제외하고 최소 비용을 가지는 색을 칠한다.

이렇게 풀었는데 잘못된 접근 방식이었다.

예를 들어, 예제 5번의 경우 3번째 집에서 최소비용으로 37을 선택하고 끝낸 채로 지나가면 4번째 집에서 29를 선택하지 못하고 89, 100을 선택하게 된다. 따라서 결과값이 최종 답보다 크게 나와서 틀리게 됐다.

😂 틀린 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
    public static int min(int past,int arr[]){
        int min = 1000;
        int index=-1;
        for(int i=0; i<3; i++){
            if(min>arr[i]&&i!=past) {
                index = i;
                min = arr[i];
            }
        }
        return index;
    }
    public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int n = Integer.parseInt(br.readLine());
         int color[][]=new int[n][3];
         int house[] = new int[n];
         int min=1000;
         for(int i=0; i<n; i++){
             StringTokenizer st = new StringTokenizer(br.readLine()," ");
             color[i][0]=Integer.parseInt(st.nextToken());
             color[i][1]=Integer.parseInt(st.nextToken());
             color[i][2]=Integer.parseInt(st.nextToken());
         }
         house[0]=min(-1,color[0]);
         for(int i=1; i<n; i++){
             house[i]=min(house[i-1],color[i]);
         }
         int sum=0;
         for(int i=0; i<n; i++){
             sum+=color[i][house[i]];
         }
         for(int i=0; i<n; i++)
             System.out.println(house[i]);
         System.out.println(sum);
    }
}

즉 이전 값을 저장한 dp 배열을 이용하여 점화식을 세우는 것이 중요하다. 언제나 동적 계획법의 핵심!

빨간색, 파란색, 초록색을 선택했을 경우를 나눠서 모두 따져봐야한다.
0 : Red / 1 : Green / 2 : Blue
dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+빨간색; //빨간색일 경우
dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+초록색; //초록색일 경우
dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+파란색; //파란색일 경우

점화식은 위와 같다.
i번째 집의 색이 빨간색인 경우, 파란색인 경우, 초록색인 경우에 따라 1 ~ i-1번째까지의 최소 비용을 계산한다.
예를 들어, 빨간색인 경우에는 빨간색 제외하고 나머지 색 중 최소값을 현재 선택된 빨간색 비용과 합한다.
즉, 한가지 색만 선택하고 지나가는 것이 아닌 모든 경우를 따져봐야하는 것이 맞다.

🔑 java 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int n = Integer.parseInt(br.readLine());
         int dp[][]=new int[n][3];
         
         for(int i=0; i<n; i++){
             StringTokenizer st = new StringTokenizer(br.readLine()," ");
             int R=Integer.parseInt(st.nextToken());
             int G=Integer.parseInt(st.nextToken());
             int B=Integer.parseInt(st.nextToken());
             
             if(i==0) {
            	 dp[0][0]=R;
            	 dp[0][1]=G;
            	 dp[0][2]=B;
             }
             else {
            	 dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+R;//빨간색일 경우
            	 dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+G;//초록색일 경우
            	 dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+B;//파란색일 경우
             }
         }
         
         int min=dp[n-1][0];
         for(int i=1; i<3; i++) {
        	 if(min>dp[n-1][i])
        		 min=dp[n-1][i];
         }
         
         System.out.println(min);
    }
}