이 문제는 처음에 문제 해석을 잘 못해서 다른 사람의 답변을 보고 풀었다.
이 문제는 n번째 집을 기준으로 n-1,n+1의 집의 색깔이 달라야한다. 즉 다시 말하면 연속된 두 집은 서로 같은 색을 칠할 수 없다. 그리고 모든 집을 칠하는 비용의 최솟값을 출력해야한다.
이때 최소값을 찾아 누적합을 구하면 26 + 49 + 13과 같이 구하면 값을 구할수 없고 모든 경로의 작은 값들을 누적합으로 계산해서 찾아야한다. 이 문제는 DP로 풀수 있다. DP의 조건은 다음과 같다.
- 큰 문제를 작은 문제로 나눌 수 있고
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다는 조건이 만족해야한다.
현재 집을 어떤 색으로 칠하냐에 따라 이전 색의 집을 정할 수 있는데 집의 수는 최소 2개이기에 2번째 집을 기준으로 생각하면 다음과 같다.
- 2번 집을 빨강으로 칠하면 1번 집은 초록 또는 파랑 중에 작은 비용으로 칠해야한다.
- 2번 집을 초록으로 칠하면 1번 집은 빨강 또는 파랑 중에 작은 비용으로 칠해야한다.
- 2번 집을 파랑으로 칠하면 1번 집은 빨강 또는 초록 중에 작은 비용으로 칠해야한다.
2번 집을 빨강으로 칠하려면 1번집은 40과 83 중에 더 작은 수인 40으로 칠해야한다. 이때 40과 49를 더하면 89라는 최소비용을 구할 수 있다. 마찬가지로 2번집을 초록으로 칠하려면 1번 집은 26과 83중에 작은 값인 26으로 칠해야한다. 따라서 26 + 60 = 86이라는 값을 구할수있다. 이때 이 더한 값을 배열에 저장하는 것을 메모이제이션이라고 한다. 이렇게 구한 값을 활용해서 3번 집의 최소비용을 구할 수 있다.
똑같은 방법으로 각각의 최소 비용을 각각 구할 수 있으며 그 결과는 다음과 같다. 따라서 조건에 맞게 모든 집을 칠하는 최소 비용은 96임을 알 수 있다. 이를 점화식으로 표현하면 다음과 같다.
dp[i][0] = dp[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = dp[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = dp[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);위의 문제를 bottom-up(for문)방식으로 구현하면 다음과 같다.
public class BOJ1149 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] dp = new int[n][3]; //4 3
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
dp[i][j] = scanner.nextInt();
}
}
// for( int[] tmp : dp){
// System.out.println(Arrays.toString(tmp));
// }
//bottom-up
for (int i = 1; i < n; i++) { //1부터 시작
dp[i][0] = dp[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = dp[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = dp[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
// for( int[] tmp : dp){
// System.out.println(Arrays.toString(tmp));
// }
int answer = Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
System.out.println(answer);
}
}