접근 방법
1. 조건에 따라 모든 집은 이웃의 색과 달라야 합니다.
2. 모든 칠해지는 경우의 수를 찾기
- 현재 빨간색으로 칠할 때 이전 집은 초록이거나 파랑이어야 합니다.
- 현재 파란색으로 칠하는 경우 이전 집은 빨간색이거나 초록이어야 합니다.
- 현재 초록색으로 칠하는 경우 이전 집은 빨간색이거나 파란색이어야 합니다.
따라서, 현재 색을 칠하기 위해서는 그 전 색깔 중에서 최소를 선택하면 됩니다. 현재 빨간 색을 칠하는 경우 이전 집은 초록이거나 파랑이어야하며 초록과 파랑 중 최소 비용을 선택하면 됩니다.
주의할 점
1. 처음으로 생각한 아이디어는 매번 최소 비용을 선택하는 방법입니다. 하지만, 이런 경우 이전 집까지의 최소 비용이 현재의 최소 비용을 보장하지는 않습니다. 따라서, 모든 칠해지는 경우의 수를 찾아 비용을 고려해야 합니다.
public class Main_1149 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
int col = 3;
int[][] maps = new int[N][col];
for (int i = 0; i < maps.length; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
maps[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] dp = new int[N][col];
dp[0][0] = maps[0][0]; dp[0][1] = maps[0][1]; dp[0][2] = maps[0][2];
for (int i = 1; i < N; i++) {
for (int j = 0; j < col; j++) {
if(j == 0) {//빨강->초록,파랑 가능
dp[i][j] = Math.min(dp[i-1][j+1], dp[i-1][j+2]) + maps[i][j];
}else if(j == 1) {//초록->빨강, 파랑 가능
dp[i][j] = Math.min(dp[i-1][0], dp[i-1][2]) + maps[i][j];
}else {//파랑->초록, 빨강 가능
dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1]) + maps[i][j];
}
}
}
int result = Integer.MAX_VALUE;
for (int i = 0; i < col; i++) {
result = Math.min(result, dp[N-1][i]);
}
System.out.println(result);
}
}
'Algorithm > 백준' 카테고리의 다른 글
[백준 BOJ] 14501 퇴사(DP/자바) (0) | 2022.10.19 |
---|---|
[백준 BOJ] 14916번 거스름돈 (자바/DP) (0) | 2022.10.18 |
[백준 BOJ] 17472 다리 만들기2(MST, BFS) - 자바 (0) | 2022.10.10 |
[BOJ 백준] 14502 연구소 - 자바 (0) | 2022.10.06 |
[백준]boj 17070 파이프 옮기기1 (0) | 2022.09.30 |