[백준] 2240 자두나무

문제보기

탑다운 방식으로 다이나믹 해주면 쉽게 풀 수 있다.

주의할 점 : 시작 전에 이동횟수를 사용해서 2 나무 밑으로 미리 이동할 수 있음!!

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

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };
	static int[] plum;
	static int t;
	static int w;
	static int max = 0;
	static int[][][] d;
	
	static int go(int time, int move, int curr) {
		if(move < 0) return 0; // 이동횟수 모두 소진시 중단 
		if(time == 1) { // 현재 시간이 1초라면 
			if(plum[1] == 1 && curr == 1) return 1; // 현재 위치와 자두 위치가 1이면 1개 획득 
			// 현재 위치가 2, 자두위치도 2인데, 이동할 수 있는 여력이 남아있다면 1개 획득 
			if(plum[1] == 2 && curr == 2 && move >= 1) return 1;
			return 0; // 그게 아니면 자두를 얻을 수 없다.
		}
		// 메모된 것이 있다면 갖다 쓰자 
		if(d[time][move][curr] != 0) {
			return d[time][move][curr];
		}
		// 획득된 자두 갯수가 담길 변수 
		int ans = 0;
		// 만약 현재 시간에 자두를 획득할 수 있다면 
		if(plum[time] == curr) {
			ans += 1; // 획득! 
			// 이동 안하고 이전 시간으로 이동 && 이동하고 이전시간으로 이동 중 더 큰 횟수를 선택하자 
			ans += Math.max(go(time-1, move, curr), go(time-1, move-1, curr == 1 ? 2 : 1));
		}else {
			// 만약 현재 시간에 자두를 획득할 수 없다면 
			// 그냥 위에처럼 이동할때 & 안할 때 중 더 큰 획득값을 택하면 된다 
			ans += Math.max(go(time-1, move, curr), go(time-1, move-1, curr == 1 ? 2 : 1));
		}
		// 메모이제이션 
		d[time][move][curr] = ans;
		return ans;
	}
	
	
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	t = ip(st.nextToken());
    	w = ip(st.nextToken());
    	plum = new int[t+1];
    	for(int i = 1 ; i <= t ; i++) {
    		plum[i] = ip(br.readLine());
    	}
    	d = new int[t+1][w+1][3];
    	int ans = 0;
    	go(t, w, 1); // 마지막 인간 자두의 위치가 1일때 
    	go(t, w, 2); // 마지막 인간 자두의 위치가 2일때
    	
		// 이동횟수는 w이하만 되면 되므로 이 중 제일 큰걸 찾아보자 (근데 이게 꼭 필요한가...? 잘 모르겠당)
    	for(int move = 0 ; move <= w ; move++) {
    		ans = Math.max(d[t][move][1], ans);
    		ans = Math.max(d[t][move][2], ans);
    	}
    	
    	System.out.println(ans);
     }
}