백준 2240번: 자두나무

문제 설명

• https://www.acmicpc.net/problem/2240
• 매 초 1번 또는 2번 나무에서 열매가 떨어집니다. 최대 W번 움직여 얻을 수 있는 열매의 최댓값을 구하는 문제입니다. 처음 시작할 때 1번나무 아래 위치하고 있습니다.

접근법

• 몇 초가 지났는지, 그리고 몇 번움직였는지를 고려해야 하기 때문에 2차원 dp배열을 설계해야 합니다.
  매 초 할수 있는 행동은 움직인다 or 움직이지 않는다두 개밖에 없습니다.
  그렇다는 건 t-1초에 움직이거나, 움직이지 않는선택을 할 수 있다는 의미이고 움직이면 t초에는 t-1초보다 움직인 횟수가 1회 증가하고 움직이지 않으면 t초에는 t-1의 움직인 횟수가 그대로 유지됩니다.
• dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-1])
  • i는 움직인 횟수, j는 시간입니다.
  • j초까지 i번 움직였다는 건 j-1초에 i번 움직인 상태에서 그대로 있거나, j-1초에 i-1번 움직인 상태에서 움직였거나 둘 중 하나입니다.
• 현재 위치, 움직인 횟수에 따라 열매 획득 여부가 달라집니다.
  • 나무가 2개밖에 없으며 처음 1번나무에서 시작하기 때문에 움직인 횟수가 짝수번이면 1번나무 아래 위치합니다.
  • 현재 2번나무 아래 있고 이번에 2번에서 열매가 떨어진다면 1. 2번나무에 그대로 서있고 열매 1개를 추가로 받거나, 2. 1번나무로 이동하고 열매의 개수는 그대로 유지하거나 둘 중 하나입니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		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];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		int[][] dp = new int[W+1][T+1];
		for (int i = 1; i < T+1; i++) {
			if(arr[i-1] == 1) {
				dp[0][i] = dp[0][i-1]+1;
			}else {
				dp[0][i] = dp[0][i-1];
			}
		}
		
		for (int j = 1; j <= T; j++) {
			for (int i = 1; i <= W; i++) {
				if(i%2 == 0) { // 현재 1번나무 아래 있음 -> i-1은 2번나무
					if(arr[j-1] == 1) { // 1번나무에서 자두가 떨어짐
						// 1번나무 밑에 그대로 있기 vs 1번나무에서 2번으로 이동하기
						dp[i][j] = Math.max(dp[i][j-1]+1, dp[i-1][j-1]); 
					}else { // 2번나무에서 자두가 떨어짐
						// 1번나무 밑에 그대로 있기 vs 1번나무에서 2번으로 이동하기
						dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-1]+1); 
					}
				}else { // 현재 2번나무 아래 있음
					if(arr[j-1] == 2) {
						// 2번나무 밑에 그대로 있기 vs 2번나무에서 1번으로 이동하기
						dp[i][j] = Math.max(dp[i][j-1]+1, dp[i-1][j-1]);
					}else { // 1번나무에서 자두가 떨어짐
						// 2번나무 밑에 그대로 있기 vs 2번나무에서 1번으로 이동하기 
						dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-1]+1); 
					}
				}
			}
		}
		
		System.out.println(dp[W][T]);
//		for (int i = 0; i < dp.length; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		

	}
}