RGB 거리

풀이

 처음에는 조합, DFS, 완전 탐색이 떠올랐다. 하지만 입력 조건 N(2 ≤ N ≤ 1,000) 때문에 시간 초과 판정이 뜰 거라고 예상했다. 따라서 DP로 방향을 틀었고 아래와 같은 점화식을 구할 수 있었다. (dp[i][x] : i번 집까지 x번 색으로 칠할 때 총 최소 비용)

dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + arr[i][R]
dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + arr[i][G]
dp[i][B] = min(dp[i-1][G], dp[i-1][R]) + arr[i][B]

시간복잡도 : O(N)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][3];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<N; i++){
            arr[i][0] += Math.min(arr[i-1][1], arr[i-1][2]);
            arr[i][1] += Math.min(arr[i-1][0], arr[i-1][2]);
            arr[i][2] += Math.min(arr[i-1][0], arr[i-1][1]);
        }
        int result = Math.min(arr[N-1][0], arr[N-1][1]);
        result = Math.min(result, arr[N-1][2]);
        bw.write(String.valueOf(result));

        bw.flush();
        bw.close();
        br.close();
    }
}

Python

import sys
N = int(input())
house_list = []
for i in range(N):
    house_list.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N):
    house_list[i][0] = min(house_list[i-1][1], house_list[i-1][2]) + house_list[i][0]
    house_list[i][1] = min(house_list[i-1][0], house_list[i-1][2]) + house_list[i][1]
    house_list[i][2] = min(house_list[i-1][0], house_list[i-1][1]) + house_list[i][2]
print(min(house_list[N-1]))