👀 문제
https://www.acmicpc.net/problem/1149
👊 도전
1. 설계
- i번째 집을 칠하기 위해서 i-1의 겹치지 않는 색깔 중 작은 값을 선택해서 칠한다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[][] dp=new int[n+1][3];
for(int i=1;i<=n;i++){
dp[i][0]=input.nextInt();
dp[i][1]=input.nextInt();
dp[i][2]=input.nextInt();
}
for(int i=1;i<=n;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((Math.min(dp[n][0], dp[n][1])), dp[n][2]));
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DP를 이용한다.
- 2번 집에 R을 칠한다면, 1번은 G 또는 B일 것이다. 이때 우리는 최소비용으로 칠해야 하므로 둘 중 작은 값을 선택하고, 2번 집에 R을 칠하면 되므로 dp[2][0]=Math.min(dp[1][1], dp[1][2])+dp[2][0]이 된다.
- 2번 집에 G, B를 칠하는 경우도 위와 같다. 따라서 2번 집이 R, G, B일 때, 색칠할 수 있는 세 가지 방법을 모두 구하면 된다. 두 번째 for문이 그 코드인데, i=2부터 시작하는 것이 더 좋을 것 같다. dp[0][0]=dp[0][1]=dp[0][2]=0이라 i=1부터 시작해도 문제가 발생하지 않았지만 혼동을 주기 쉬울 것 같다.
👏 해결 완료!
참고
- [JAVA] 백준 알고리즘 1149 RGB거리 https://ggmouse.tistory.com/420
- [알고리즘] 백준 1149번 https://baked-corn.tistory.com/78