[JAVA] 백준 알고리즘 1149 RGB거리

 

 

 

문제

 

 

 

 

코드

 

 

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		int[][] dp = new int[T+1][3];
		for(int i=1; i<=T; i++)
		{
			dp[i][0] = sc.nextInt(); // red
			dp[i][1] = sc.nextInt(); // green
			dp[i][2] = sc.nextInt(); // blue
		}
		
		for(int i=2; i<=T; i++)
		{
			dp[i][0] += Math.min(dp[i-1][1], dp[i-1][2]);
			dp[i][1] += Math.min(dp[i-1][0], dp[i-1][2]);
			dp[i][2] += Math.min(dp[i-1][0], dp[i-1][1]);
		}
		
		System.out.println(Math.min(dp[T][0], Math.min(dp[T][1], dp[T][2])));
	}
}

 

 

 

 

설명

 

현재 칠할 수 있는 색상이 빨강일 경우는 : dp[i][0]

1. 바이전에 초록색으로 칠했을 때 지금까지 칠한 비용 + 현재 빨강색으로 칠할 비용 : dp[i-1][1] + dp[i][0]

2. 바로 이전에 파랑색으로 칠했을 때 지금까지 칠한 비용 + 현재 빨강색으로 칠할 비용 : dp[i-1][2] + dp[i][0]

를 비교해서 최소값으로 선택한다.

 

마찬 가지로 현재 칠할 수 있는 색상이 초록색과 파랑색일 경우에는 그 외 다른 색상과 비교해서 최소값으로 선택한다.

 

 

 

 

출처

 

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