풀이 방법
다이나믹 프로그래밍을 사용해서 풀이했다.
중요한 게 매우 큰 점프를 한번만 사용할 수 있다는 것이다.
그래서 매우 큰 점프를 사용할 수 있는 모든 경우의 수에 넣어주었다.
나머지는 DP의 Bottom-Up 방식으로 풀이하면 된다.
내 코드
package com.company;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
int array[][] = new int[N + 1][2];
array[0][0] = 5000;
array[0][1] = 5000;
for (int i = 1; i < N; i++) {
st = new StringTokenizer(br.readLine());
array[i][0] = Integer.parseInt(st.nextToken());
array[i][1] = Integer.parseInt(st.nextToken());
}
array[N][0] = 0;
array[N][1] = 0;
int K = Integer.parseInt(br.readLine());
int min = (int) 1e9;
for (int j = 0; j <= N; j++) {
int d[] = new int[N + 1];
for (int i = 2; i <= N; i++) {
d[i] = Math.min(d[i - 1] + array[i - 1][0], d[i - 2] + array[i - 2][1]);
if (i == j && j > 3) {
d[i] = Math.min(d[i - 3] + K, d[i]);
}
}
min = Math.min(d[N], min);
}
System.out.println(min);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
듣보잡 - 1764번 (0) | 2021.10.06 |
---|---|
평범한 배낭 - 12865번 (0) | 2021.10.05 |
스티커 - 9465번 (0) | 2021.10.05 |
좋은 수열 - 2661번 (0) | 2021.10.04 |
말이 되고픈 원숭이 - 1600번 (0) | 2021.10.04 |