[백준 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. 마지막까지 구해서 그 중 최소 금액이 답이 될 것이다.

 

코드