[백준 알고리즘] 백준 1149번 RGB거리 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1149번 RGB거리 자바(Java)

1) 문제번호 : 1149번

 

2) 문제 출처

www.acmicpc.net/problem/1149

1149번: RGB거리

 

2. 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

3. 제약사항

- 

4. 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

5. 출력

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

 

6. 풀이

- 입력을 받으면서 최솟값들을 입력받으면 된다.

- 이 문제에서 규칙은 서로 인접한 색끼리 겹치면 안된다. 즉, 빨 녹 파나 빨 녹 빨 이렇게 겹치면 안된다.

- 그래서, 첫 번째부터 최솟값을 찾은 다음, 두 번째 줄에서 첫 번째 색상을 제외한 것 중에 최솟값을 구하여 더해주면서 DP를 채우면 된다.

 

7. 소스 코드

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

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 집의 수
		int[][] DP = new int[N+1][3];
		
		for(int i=1;i<=N;i++) {
			int R = sc.nextInt();
			int G = sc.nextInt();
			int B = sc.nextInt();
			
			DP[i][0] = Math.min(DP[i-1][1], DP[i-1][2]) + R;
			DP[i][1] = Math.min(DP[i-1][0], DP[i-1][2]) + G;
			DP[i][2] = Math.min(DP[i-1][0], DP[i-1][1]) + B;
		}
		
		System.out.println(Math.min(DP[N][0], Math.min(DP[N][1], DP[N][2])));
	}
}

 

---