백준 1149(RGB 거리) - Python(파이썬) - DP

1149번: RGB거리

예제 풀이

	0	1	2
array[0]	array[0][0] = 26	array[0][1]=40	array[0][2]=83
array[1]	min (array[1][0]+array[0][1], array[1][0]+array[0][2]) = ( 49+40,49+83 ) = 89	min (array[1][1]+array[0][0], array[1][1]+array[0][2]) = ( 60+26,60+83 ) = 86	min (array[1][2]+array[0][0], array[1][2]+array[0][1]) = ( 57+26,57+40 ) = 83
array[2]	min (array[2][0]+array[0][1], array[2][0]+array[0][2]) = ( 13+86,13+86 ) = 96	min (array[2][1]+array[0][0], array[2][1]+array[0][2]) = ( 89+89,89+83 ) = 172	min (array[2][2]+array[0][0], array[2][2]+array[0][1]) = ( 99+89,99+86 ) = 185

문제 풀이

예를 들어 현재 행의 빨간색의 비용의 최솟값을 구한다고 할 떄, 전행에 초록색과 파란색일 때의 비용을 각각 더했을 때의 최솟값을 저장한다. 이런식으로 n-1번 실행한 후에 마지막 행에 최솟값을 출력한다.

💻Python(파이썬)

import sys

n = int(sys.stdin.readline())
array = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

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

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

💻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());
        int[][] array = new int[N][3];
        for(int i=0;i<N;i++){
            //string배열로 받아들이는걸 int 배열로 변경(string -> stream -> array
            array[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        int min = 0;
        for(int i=1;i<N;i++){
            array[i][0] = Math.min(array[i][0]+array[i-1][1],array[i][0]+array[i-1][2]);
            array[i][1]=Math.min(array[i][1]+array[i-1][0],array[i][1]+array[i-1][2]);
            array[i][2] = Math.min(array[i][2]+array[i-1][0],array[i][2]+array[i-1][1]);
            if(i==N-1){
                min = Math.min(Math.min(array[i][0],array[i][1]),array[i][2]);
            }
        }
        System.out.println(min);
    }
}