문제
https://www.acmicpc.net/problem/2240
문제해설
자두나무 2그루에서 자두가 떨어진다.
떨어지는 열매를 최대한 많이 받아 먹으려고 한다.
열매는 떨어지는 것만 받아 먹을 수 있으며
1, 2번 나무 간 거리를 1초안에 움직일 수 있다.
또한 움직일 수 있는 횟수가 주어진다.
문제풀이
dp라는 느낌은 났지만 처음에 2차원 dp만을 생각해서 풀기가 힘들었다.
2차원으로도 잘 짜면 가능할 것 같지만 내 수준에서는 아직 안되나보다.
문제에서 주어진 변수를 잘 생각해보면
우선 자두가 떨어지는 시간, 이동 횟수, 몇번 나무인지 이렇게 총 3가지 변수가 필요하다. 그래서 이 3가지를 이용해 3차원 dp를 만들었다.
dp[자두가 떨어지는 시간][이동한 횟수][나무의 번호] = 먹은 자두 수
이걸 토대로 생각을 해보면
1
2
dp[a][b][1] = dp[a-1][b][1] + dp[a-1][b-1][2]
dp[a][b][2] = dp[a-1][b-1][1] + dp[a-1][b][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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static int t, w;
public static ArrayList<Integer> arr = new ArrayList<>();
public static int[][][] dp = new int[1001][31][3];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
t = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
arr.add(-1);
for (int i = 0; i < t; i++) {
int tree = Integer.parseInt(br.readLine());
arr.add(tree);
}
dp[0][0][1] = 0;
dp[0][0][2] = 0;
int res = 0;
for (int i = 1; i <= t; i++) {
for (int j = 0; j <= w; j++) { //0은 움직이지 않는것
if (arr.get(i) == 1) {
if (j == 0) {
dp[i][j][1] = dp[i - 1][j][1] + 1;
continue;
}
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + 1;
dp[i][j][2] = Math.max(dp[i - 1][j][2], dp[i - 1][j - 1][1]);
res = Math.max(dp[i][j][1], dp[i][j][2]);
} else {
if (j == 0) {
dp[i][j][1] = dp[i - 1][j][1];
continue;
}
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][2]);
dp[i][j][2] = Math.max(dp[i - 1][j][2], dp[i - 1][j - 1][1]) + 1;
res = Math.max(dp[i][j][1], dp[i][j][2]);
}
}
}
System.out.println(res);
}
}