본문 바로가기
알고리즘(Java)/다이나믹 프로그래밍(동적계획법)

백준 1149 RGB

Gongdel 2017. 12. 11. 10:02

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

예제 입력 

3
26 40 83
49 60 57
13 89 99

예제 출력 

96

힌트

출처

알고리즘 분류

 

개념설명:

 

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220785383050&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Dt%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dweb%26cd%3D1%26ved%3D0ahUKEwiiga_WzYDYAhWGJZQKHfKfAaMQFggmMAA%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252Foccidere%252F220785383050%26usg%3DAOvVaw0RFEwjtg0y4hX25kZXCnpn

 

 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int [][] d = new int[n + 1][3];// n + 1은 집의 순번은 1부터 시작하기 위함, 3 =  R G B
		int [][] a = new int[n + 1][3];
		
		for(int i = 1; i <= n; i++){
			for(int j = 0; j < 3; j++){
				a[i][j] = sc.nextInt();
			}
		}
		sc.close();
		
		d[0][0] = d[0][1] = d[0][2] = a[0][0] = a[0][1] = a[0][2] = 0;
		
		for(int i = 1; i <= n; i++){
			d[i][0] = Min(d[i - 1][1], d[i - 1][2]) + a[i][0];
			d[i][1] = Min(d[i - 1][0], d[i - 1][2]) + a[i][1];
			d[i][2] = Min(d[i - 1][0], d[i - 1][1]) + a[i][2];
		}
		
		System.out.println(Min(Min(d[n][0], d[n][1]), d[n][2]));
	}
	
	public static int Min(int a, int b){
		return a < b? a: b;
	}
}

'알고리즘(Java) > 다이나믹 프로그래밍(동적계획법)' 카테고리의 다른 글

백준 1463 1로 만들기  (0) 2017.12.14
백준 2579 계단오르기  (0) 2017.12.13
백준 1932 숫자삼각형  (0) 2017.12.12

'알고리즘(Java)/다이나믹 프로그래밍(동적계획법)' Related Articles

티스토리툴바