[Python/Java] 백준 1149번: RGB거리

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

 

 

[풀이]

각 지붕에 대해 색을 칠할 수 있으며, 

빨강, 노랑, 파랑 중 최소한의 비용으로 칠하고, 동시에 좌/우에 위치한 지붕과는 색깔이 달라야 한다.

 

일단 위의 사진에 있는 코드처럼 완탐으로 시도해보았다.

 

 

안되더라, 시간초과 뜨더라.

그래서 가지치기를 할 수 있는 방법에 대해 고민해보았다.

 

메모이제이션을 활용하였다.

 

 

 

[코드]

- Python

n = int(input())
color = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n)]
dp[0] = color[0][:]

for i in range(1, n):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + color[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + color[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + color[i][2]

print(min(dp[n - 1]))

 

 

- Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[][] color = new int[n][3];
        int[][] dp = new int[n][3];

        for (int i = 0; i < n; i++) {
            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());
        }

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

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

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

 

 

 

 

[시간복잡도]

시간복잡도: O(N)

공간복잡도: O(N)