★ 백준/1149 RGB거리 / 다이나믹 프로그래밍 ,메모이제이션

RGB거리 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

88412

46869

34983

52.386%

문제

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

출력

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

예제 입력 1 복사

3
26 40 83
49 60 57
13 89 99

예제 출력 1 복사

96

예제 입력 2 복사

3
1 100 100
100 1 100
100 100 1

예제 출력 2 복사

3

예제 입력 3 복사

3
1 100 100
100 100 100
1 100 100

예제 출력 3 복사

102

예제 입력 4 복사

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4 복사

208

---

풀이

시간제한과 메모리제한으로 다이나믹 프로그래밍을 써야하는지 판단하는것과

메모이제이션으로 dp배열을 어떻게 채울지 손으로 직접 그려가면서 체크하는것이 중요한거같다.

 

/*
조합의 동작방식 느낌인데, 이전것만 아니면 골랐던거를 다시골라도 되는 조합이다. 집의수가 1000개까지 있으니 O(2^1000)은 시간초과를 할것이다.
dp배열을 어떻게 구성할것인지, 어떤 로직인지 생각하는게 중요한거같다.
dp배열에는 현재 집의 해당 인덱스의 색을 선택했을경우 비용의 최솟값을 저장해준다.
2번째 집에서 레드칸에 들어갈 최솟값은   그린(1번집)+레드(2번집) 의 겅우와 블루(1번집)+레드(2번집)의 비용합중 더 작은값을 적으면 될것이다.
그렇게 n번째 집까지의 각 색깔별 비용최소값을 적고 마지막에 n번째줄의 3가지 색중 최소값을 출력해준다.
 */

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    /*
    조합의 동작방식 느낌인데, 이전것만 아니면 골랐던거를 다시골라도 되는 조합이다. 집의수가 1000개까지 있으니 O(2^1000)은 시간초과를 할것이다.
    dp배열을 어떻게 구성할것인지, 어떤 로직인지 생각하는게 중요한거같다.
    dp배열에는 현재 집의 해당 인덱스의 색을 선택했을경우 비용의 최솟값을 저장해준다.
    2번째 집에서 레드칸에 들어갈 최솟값은   그린(1번집)+레드(2번집) 의 겅우와 블루(1번집)+레드(2번집)의 비용합중 더 작은값을 적으면 될것이다.
    그렇게 n번째 집까지의 각 색깔별 비용최소값을 적고 마지막에 n번째줄의 3가지 색중 최소값을 출력해준다.
     */

    static int n;
    static int[][] cost;
    static int[][] dp;


    public static void main(String[] args) throws IOException {

        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        n = Integer.parseInt(br.readLine());
        cost = new int[n][3];
        dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            cost[i][0] = Integer.parseInt(input[0]);
            cost[i][1] = Integer.parseInt(input[1]);
            cost[i][2] = Integer.parseInt(input[2]);
        }
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

    }

    static void solve() throws IOException {
        //바텀업 방식으로 dp배열을 채운다.

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == 0) { //레드일때 ,  (이전집 블루비용 + 현재집 레드비용) vs(이전집 그린비용 + 현재집 레드비용) 중 최소값을 저장
                    dp[i][0] = Math.min(dp[i - 1][1] + cost[i][0], dp[i - 1][2] + cost[i][0]);
                }
                if (j == 1) {
                    dp[i][1] = Math.min(dp[i - 1][0] + cost[i][1], dp[i - 1][2] + cost[i][1]);
                }
                if (j == 2) {
                    dp[i][2] = Math.min(dp[i - 1][0] + cost[i][2], dp[i - 1][1] + cost[i][2]);
                }
            }
        }

        bw.write(Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2])+"");


    }


}

 

https://st-lab.tistory.com/128

[백준] 1149번 : RGB거리 - JAVA[자바]