Java 1149 RGB거리

 

 

풀이 :

같은 색깔의 집이 연속하면 안된다는 조건만 잘 지키면 어렵지 않게 풀 수 있는 문제였습니다.

그리고 처음 시작하는 경우가 3가지 있기 때문에 각각의 시작점에서 구한 최소값들을 비교하여 그 중에서 제일 작은 값을 출력하면 됩니다.

dp문제이기에 메모이제이션을 할 배열을 선언하고 최종값에 도달하기 전까지의 값들을 저장해주며 연산을 이어나가면 됩니다.

 

dp문제를 풀 때는 내가 당장 어떤 조건문이나 반복문을 통해 원하는 값을 한방에 도출해낸다는 생각보단 내가 원하는 값들을 도출할 수 있는 식을 세워서 그 식들이 내가 원하는 값을 구해준단 생각을 가지고 접근하는 게 중요하고 dp 문제가 어려우신 분이라면 제일 중요한 건 많이 풀어봐야 감을 잡을 수 있습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[][] house = new int[n][3];
        int[][] dp = new int[n][3];
        StringTokenizer st;

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            house[i][0] = Integer.parseInt(st.nextToken());
            house[i][1] = Integer.parseInt(st.nextToken());
            house[i][2] = Integer.parseInt(st.nextToken());
        }

        dp[0][0] = house[0][0];
        dp[0][1] = house[0][1];
        dp[0][2] = house[0][2];

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + house[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + house[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + house[i][2];
        }

        int result = Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
        System.out.println(result);

    }
}