[백준] 1149번: RGB거리

문제 링크

 

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

1149번: RGB거리

 

풀이 시간

 

25분

 

풀이 방향성

 

백트래킹->(시간초과) -> DP->통과

 

정답 코드

 

1. 파이썬 

import sys
sys_input=sys.stdin.readline

n=int(sys_input())
arr=[list(map(int,sys_input().rstrip().split())) for _ in range(n)]
dp=[[arr[0][0],arr[0][1],arr[0][2]]]

for i in range(1,n):
    cur=[]
    cur.append(min(dp[-1][1],dp[-1][2])+arr[i][0])
    cur.append(min(dp[-1][0],dp[-1][2])+arr[i][1])
    cur.append(min(dp[-1][0],dp[-1][1])+arr[i][2])

    dp.append(cur)

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

 

2. 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));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[][] dp = new int[n][3];

        for (int i = 0; i < 3; i++) {
            dp[0][i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + Integer.parseInt(st.nextToken());
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + Integer.parseInt(st.nextToken());
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + Integer.parseInt(st.nextToken());
        }

        System.out.println(Arrays.stream(dp[n - 1]).min().getAsInt());
    }
}