[Boj2240] 자두나무

첫 번째 시도 (성공)

DP 테이블 정의

dp[t][w][k] = i 초일때 k번 나무에서 현재까지 w만큼 움직여서 얻을 수 있는 최대 자두의 수

 

DP 테이블 초기화 

// 1초에 자두가 떨어지는 나무의 위치에 따라 초기화
if(tree[0] == 1) {
	dp[0][0][0] = 1; 
}else{
    dp[0][1][1] = 1; 
}

// 주어진 시간동안 움직이지 않고 계속 제자리에 서 있는 경우
for(int t=1; t<T; t++) {
    dp[t][0][0] = (tree[t] == 1) ? dp[t-1][0][0] + 1 : dp[t-1][0][0];
}

 

점화식 

1초 전과 위치와 비교해서 움직이는 경우(dp[t-1][w-1][(i+1) % 2])와 현재 자리를 지키는 경우(dp[t-1][w][i]) 얻을 수 있는 자두의 최대 개수 + 현재 위치에 떨어지는 자두(cur) 값으로 갱신

dp[t][w][i] = Math.max(dp[t-1][w-1][(i+1) % 2], dp[t-1][w][i]) + cur;

 

전체 코드

import java.io.*;
import java.util.*; 

public class Main {
	
	static int T, W, tree[]; 
	
	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()); // 최대 움직일 수 있는 
		
		tree = new int[T];
		
		for(int i=0; i<T; i++) {
			tree[i] = Integer.parseInt(br.readLine()); 
		}
		
		int[][][] dp = new int[T][W+1][2];
		
		for(int t=0; t<T; t++) {
			for(int w=0; w<=W; w++) {
				Arrays.fill(dp[t][w], 0);
			}
		}
		
		// 초기화
		dp[0][0][0] = (tree[0] == 1) ? 1 : 0;
		if(tree[0] == 2) {
			dp[0][1][1] = 1; 
		}
		
		for(int t=1; t<T; t++) {
			dp[t][0][0] = (tree[t] == 1) ? dp[t-1][0][0] + 1 : dp[t-1][0][0];
		}
		
		for(int t=1; t<T; t++) {
			for(int w=1; w<=W; w++) {
				
				for(int i=0; i<2; i++) {
					int cur = (tree[t] == i+1) ? 1 : 0; 
					
					dp[t][w][i] = Math.max(dp[t-1][w-1][(i+1) % 2], dp[t-1][w][i]) + cur;
					
				}
			}
		}
		
		int answer = 0; 
		for(int w=0; w<=W; w++) {
			for(int i=0; i<2; i++) {
				answer = Math.max(answer, dp[T-1][w][i]);
			}
		}
		
		System.out.println(answer);
	}

}