[백준 with JAVA] 1149번 : RGB 거리 - DP

 

1149번: RGB거리

1149번: RGB거리

 

 

 

문제

 

 

 

 

문제 접근

문제 조건을 보면

결국 i번째 집이 있다고 했을 때

 

color[i - 1] ≠ color[i] && color[i] ≠ color[i + 1]

 

이 성립하면 되는 문제입니다.

 

조건만 봐도 바로 점화식이 나와버리는 문제였습니다.

 

한 가지 더 생각을 하자면

마지막 선택한 집이

Red 일 경우

Green 일 경우

Blue 일 경우

로 3가지 구분 지어서 점화식을 만든 후에 마지막에 비교해주시면 되겠습니다.

 

 

 

 

나의 아쉬운 점

 

문제 접근법도 나쁘지 않고 각 색깔별로 구분지어서 배열을 만들어서 부분 문제로 푸는 것도 성공적이었습니다.

하지만 색깔과 색깔을 비교하기 위해 for문이 많이 들어가게 됐는데 실제로 N * 3 * 3 정도 연산에 불과하지만

for문을 다른 방법으로 충분히 뺄 수 있는 방법들이 있었습니다.

 

 

실질적으로 연산횟수는 똑같다고 할 수 있지만 깔끔하지 않은 코드입니다.

for (int i = 1; i < N; i++) {
    for (int j = 1; j <= 3; j++) {
        for (int k = 1; k <= 3; k++) {
            if (k != j) dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + houses[i][j]);
        }
    }
}

 

 

이 코드를 바꾼다면 다음과 같이 바꿀 수 있습니다.

훨씬 보기 좋고 깔끔합니다.

또한 if문이 없어져서 조금이라도 더 효율적이라고 할 수 있습니다.

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

밑은 저의 코드입니다.

 

 

 

 

RGB 거리 - 내 코드

 

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

public class Main {

    static int N;
    static int[][] houses;
    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());

        houses = new int[N][3 + 1];
        dp = new int[N][4];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            for (int j = 1; j <= 3; j++) {
                houses[i][j] = Integer.parseInt(st.nextToken());
                if (i == 0) dp[0][j] = houses[0][j];
            }
        }

        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int k = 1; k <= 3; k++) {
                    if (k != j) dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + houses[i][j]);
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= 3; i++) {
            answer = Math.min(dp[N - 1][i], answer);
        }
        System.out.println(answer);
    }
}