boj)1149 - RGB 거리
2020. 9. 19. 01:41ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_1149 {
static int[][] dp;
static int[][] val; // 페인트 가격
static StringTokenizer st;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp = new int[n][3];
val = new int[n][3];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
val[i][0] = Integer.parseInt(st.nextToken()); // R
val[i][1] = Integer.parseInt(st.nextToken()); // G
val[i][2] = Integer.parseInt(st.nextToken()); // B
}
dp[0][0] = val[0][0]; dp[0][1] = val[0][1]; dp[0][2] = val[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + val[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + val[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + val[i][2];
}
System.out.println(Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]));
}
}
- 다시 보니까 어려워 보이지 않는데 왜 생각이 딱 안떨어질까 ,,
- 조건에서 연속 ? -> 이중배열이 떠오를 수 있다.
- dp[i][0~2] => i번째가 0~2의 색깔일때 까지 페인트를 칠한 최솟값
- i번째가 0으로 칠했다면, 그 전에 집은 1또는 2로 칠했다.
- dp[i-1][1], dp[i-1][2] 중 최솟값 + i번째 집의 페인트 가격
'PS > boj' 카테고리의 다른 글
boj)11057 - 오르막수 (0) | 2020.09.19 |
---|---|
boj)1309 - 동물원 (0) | 2020.09.19 |
boj)2225 - 합분해 (0) | 2020.09.18 |
boj)1699 - 제곱수 (0) | 2020.09.18 |
boj)1912 - 연속합 (0) | 2020.09.18 |