백준 2240번: 자두나무 (G5)

문제

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

---

풀이 방법

문제는 크게 세가지의 키워드로 분류할 수 있다.
자두가 떨어지는 T초, 최대 움직일 수 있는 W번, 자두가 위치할 수 있는 위치번호(1, 2번)


예제 입력을 표로 나타내보면 다음과 같다.

현재 2초이고, 1의 위치에 있다고 하자. 얘가 이전에 있을 수 있는 위치는 두 군데다.

1. 1초에 1의 위치에 있을 경우

2. 1초에 2의 위치에 있을 경우 (이 경우 이동을 해야하기 때문에 현재 위치의 이동횟수-1 을 가진다)

DP[현재 위치][시간][이동 횟수]
DP[1][2][W] = Math.max(DP[1][1][W], DP[2][1][W - 1]) + (해당 초에 해당 위치에 자두가 떨어지면 +1, 아니면 +0)

// 자두가 1번 자두나무에 떨어질 경우.

dp[1][T][W] = MAX(dp[1][T-1][W] + 1, dp[2][T-1][W-1] + 1)

// 자두가 2번 자두나무에 떨어질 경우.

dp[2][T][W] = MAx(dp[2][T-1][W] + 1, dp[1][T-1][W-1] + 1)

그리고 위의 점화식을 반복문으로 구성하기 위해, 초기 이동횟수를 0이 아닌 1로 잡았다.

---

코드

package day0203;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_G5_2240_자두나무 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());	// 시간(초)
		int W = Integer.parseInt(st.nextToken());	// 최대 이동횟수
		int[] arr = new int[T+1];
		
		for(int i=1; i<=T; i++) {
			arr[i] = Integer.parseInt(br.readLine());	// 떨어지는 자두의 나무위치 정보
		}
		
		int[][][] dp = new int[3][T+1][W+2];	// DP[현재위치][떨어지는 시간][이동횟수]
		
		for(int i=1; i<=T; i++) {
			for(int j=1; j<=W+1; j++) {		// 초기 이동횟수를 0이 아닌 1로 잡음
				if(arr[i]==1) {		// 자두가 나무1에 떨어지는 경우
					dp[1][i][j] = Math.max(dp[1][i-1][j], dp[2][i-1][j-1]) + 1;		// 자두가 1에 위치했을 때
					dp[2][i][j] = Math.max(dp[2][i-1][j], dp[1][i-1][j-1]);			// 자두가 2에 위치했을 때
				} else {		// 자두가 나무2에 떨어지는 경우
					if (i==1 && j==1) continue;
					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]) + 1;	// 자두가 2에 위치했을 때
				}
			}
		}
		
		int ans = 0;	// 자두가 받을 수 있는 자두의 최대 개수
		for(int i=1; i<=W+1; i++) {
			ans = Math.max(ans, Math.max(dp[1][T][i], dp[2][T][i]));
		}
		
		System.out.println(ans);
	}
}