[BaekJoon] 2240 자두나무 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/2240

2.  문제

요약

• 자두나무를 심어두고, 열리는 자두를 먹고는 하는데, 자두가 떨어질 때까지 기다린 다음 떨어지는 자두를 받아서 먹고는 합니다.
• 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 합니다.
• 매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 되고, 열매가 떨어지는 순간, 그 나무의 아래에 서 있으면 그 열매를 받아먹을 수 있습니다.
• 두 나무는 그다지 멀리 떨어져 있지 않아 하나의 나무 아래에 서 있다가 다른 나무 아래로 1초보다 짧은 시간에 움직일 수 있습니다.
• 자두는 T초 동안 떨어지게 되고 최대 W번만 움직이려고 합니다.
• 처음에 1번 자두나무 아래에 위치해 있고 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 받을 수 있는 자두의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 정수 T와 1보다 크거나 같고 30보다 작거나 같은 정수 N이 주어지고 두 번째 줄부터 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어집니다.
• 출력: 첫 번째 줄에 받을 수 있는 자두의 최대 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getMaxNum(int t, int w, int[] tree_nums) {
		int result = 0;
		int[][][] dp = new int[3][t + 1][w + 2];
		for(int i = 1; i <= t; i++) {
			for(int j = 1; j <= w + 1; j++) {
				if(tree_nums[i] == 1) {
					dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]) + 1;
					dp[2][i][j] = Math.max(dp[2][i - 1][j], dp[1][i - 1][j - 1]);
				} else {
					if(i == 1 && j == 1) {
						continue;
					}
					dp[1][i][j] = Math.max(dp[1][i - 1][j], dp[2][i - 1][j - 1]);
					dp[2][i][j] = Math.max(dp[2][i - 1][j], dp[1][i - 1][j - 1]) + 1;
				}
			}
		}
		for(int i = 1; i <= w + 1; i++) {
			result = Math.max(result, Math.max(dp[1][t][i], dp[2][t][i]));
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int t = Integer.parseInt(input[0]);
		int w = Integer.parseInt(input[1]);
		int[] tree_nums = new int[t + 1];
		for(int i = 1; i < tree_nums.length; i++) {
			tree_nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxNum(t, w, tree_nums) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 메모이제이션을 위한 3차원 배열 dp를 생성하는데 각 차원이 의미하는 바는 아래와 같습니다.
  • dp[2][t][w] = dp[현재 위치한 나무][시간][이동 횟수]
• 현재 시각 이전에 위치할 수 있는 곳은 1 또는 2입니다.
• 현재 시각이 3초이고 2의 위치에 있다면, 2초에 1의 위치에 있을 경우와 2의 위치에 있을 경우 두 경우가 있을 것입니다.
• 만약 2초에 1의 위치에 있었다면 2 위치로 이동하였기 때문에 w에서 1을 빼주어야 합니다.
• 만약 2초에 2의 위치에 있었다면 따로 이동하지 않았으므로 w에서 1을 빼줄 필요가 없어집니다.
• 3초에 2의 위치에 있을 때의 dp값을 생각해보면 아래와 같이 표현할 수 있습니다.
  • dp[2][3][w] = max(dp[1][2][w - 1], dp[2][2][w]) + (1 또는 0)
    • 만약 3초에 2의 위치에서 자두가 떨어진다면 받는 자두의 개수가 1 증가하므로 1을 더해주고 그렇지 않다면 0을 더합니다.
• 위 예시를 통해 아래와 같은 점화식이 발생합니다.
  • dp[1][t][w] = max(dp[1][t - 1][w], dp[2][t - 1][w - 1]) + (1 또는 0)
  • dp[2][t][w] = max(dp[1][t - 1][w - 1], dp[2][t - 1][w]) + (1 또는 0)
• 위 점화식을 이용하여 받을 수 있는 자두의 최대 개수를 구합니다.
• 위 코드에서 dp 배열을 dp[3][t + 1][w + 2]라고 정의했는데, 이는 위 점화식을 반복문을 통해 이용할 것이므로 초기 이동횟수를 0이 아닌 1로 잡았기 때문입니다.