[백준 1149번] RGB 거리 - java

문제 설명

1. 집의 수 N을 입력받고, 집은 R, G, B 세 가지 색으로 칠해질 수 있다.

2. 총 N개의 집에 대해 R, G, B 색으로 칠하는 금액을 입력받는다.

3. 현재 집을 기준으로 위, 아래 집과 색이 달라야 한다.

3. 전체 집을 칠하는 데 가장 적게 드는 금액을 return 한다.

풀이 과정

 1. 전형적이고 간단한 DP문제이다.

 2. 문제에서 현재 집 기준으로 위, 아래 집과 색이 달라야 한다고 하는데, 굳이 위아래 다 구할 필요 없이, 현재 집 기준으로 아래에 위치한 집과 색이 다르게 구하면 될 것이다.

 3. 현재 칠할 장소를 기준으로 가장 적은 금액으로 칠한 장소를 구하면 될 것이다.

ex) 

 

	빨강	초록	파랑
1번집	5	3	2
2번집	6	1	3
3번집	7	5	4
4번집	1	6	2
5번집	7	4	9

1번 집을 빨강, 초록, 파랑색으로 칠하는데 드는 돈은 각각 5, 3, 2원이다.

  -----

2번 집을 빨강색으로 칠하려 하면, 그 전인 1번 집은 초록색이거나 파랑색이어야 한다.

그 중 최소 금액은 파랑색으로 칠한 2원일 것이다.   <- 2번 집이 빨강색인 최소 금액 = 6 + 2 = 8원

2번 집을 초록색으로 칠하려 하면, 그 전인 1번 집은 빨강색이거나 파랑색이어야 한다.

그 중 최소 금액은 파랑색으로 칠한 2원일 것이다.   <- 2번 집이 초록색인 최소 금액 = 1 + 2 = 3원

2번 집을 파랑색으로 칠하려 하면, 그 전인 1번 집은 빨강색이거나 초록색이어야 한다.

그 중 최소 금액은 초록색으로 칠한 3원일 것이다.   <- 2번 집이 파랑색인 최소 금액 = 3 + 3 = 6원

 -----

3번 집을 빨강색으로 칠하려 하면, 그 전인 2번 집은 초록색이거나 파랑색이어야 한다.

그 중 최소 금액은 초록색으로 칠한 (1+2)=3원일 것이다.   <- 2번 집이 빨강색인 최소 금액 = 7 + (1+2) = 10원

3번 집을 초록색으로 칠하려 하면, 그 전인 2번 집은 빨강색이거나 파랑색이어야 한다.

그 중 최소 금액은 파랑색으로 칠한 (3+3)=6원일 것이다.   <- 2번 집이 초록색인 최소 금액 = 5 + (3+3) = 11원

3번 집을 파랑색으로 칠하려 하면, 그 전인 2번 집은 빨강색이거나 초록색이어야 한다.

그 중 최소 금액은 초록색으로 칠한 (1+2)=3원일 것이다.   <- 2번 집이 파랑색인 최소 금액 = 3 + (1+2) = 6원

 -----

그럼 4번째 집의 색을 칠하는데 드는 전체 금액을 구하려면 당연히

4번째 집을 칠하는데 드는 돈 + 3번째 집을 칠하는데 드는 최소 돈 <- 이렇게 구하면 된다.

 

 4. 마지막까지 구해서 그 중 최소 금액이 답이 될 것이다.

 

코드

	import java.util.*;
	public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = sc.nextInt();
	int costPer[][] = new int[N][3]; // 각각의 집마다 Red, Green, Blue를 칠하는 데에 필요한 금액을 구한다.
	int costAll[][] = new int[N][3]; // 배열의 첫 번 째 인자까지 칠해진 전체 금액 costAll
	for(int i=0; i<N; i++) { // R G B의 각각 가격을 입력받는다.
	costPer[i][0] = sc.nextInt();
	costPer[i][1] = sc.nextInt();
	costPer[i][2] = sc.nextInt();
	}
	costAll[0][0] = costPer[0][0]; // 맨 윗 집의 색을 칠하는 데에 들어가는 전체 금액은, 당연히 처음 입력받은 금액이다.
	costAll[0][1] = costPer[0][1];
	costAll[0][2] = costPer[0][2];
	for(int i=1; i<N; i++) { // 그리고 두 번째 집부터는 맨 윗 집의 전체 가격중 최소 금액에서 추가로 더해질 것이다.
	costAll[i][0] = costPer[i][0] + Math.min(costAll[i-1][1], costAll[i-1][2]); // 내위치기준 윗 집까지 구한 전체 금액 중 작은 것을 선택해 현재 위치를 구하는데 필요한 값에 더해주면 된다.
	costAll[i][1] = costPer[i][1] + Math.min(costAll[i-1][0], costAll[i-1][2]); // 0, 1, 2 <- R, G, B 세 색에 대해 맨 위로부터 시작해서 전체 금액을 하나씩 구해주면 된다.
	costAll[i][2] = costPer[i][2] + Math.min(costAll[i-1][1], costAll[i-1][0]);
	}
	int ans = Math.min(Math.min(costAll[N-1][0], costAll[N-1][1]), costAll[N-1][2]); // 그 중 가장 작은 금액이 드는 경우가 ans가 된다.
	System.out.println(ans);
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub