BOJ) 자두나무 (2240 번)

자두나무

2240번: 자두나무

 

처음 위치 1을 기준으로 자두나무에서 떨어지는 열매를 최대한 받을 수 있는 개수를 구하는 문제다.

자두나무는 1과 2 위치에만 있고, 1초마다 떨어지는 위치 정보가 주어진다.

DP를 이용해서 이 문제를 풀었다.

 

DP의 인덱스는 시간과 움직이는 횟수를 가진다.1초에 n번을 움직였을 때, 가장 큰 값을 저장해나간다.이동한 횟수가 짝수일 때와 홀수일 때를 나누어주었다.for문 하나에서 인덱스만 각각 구해서 돌릴 수 있겠지만, if문을 통해 w를 넘는지 확인해주어야 하기 때문에 조금 더 가시적으로 구분하기 위해 나누었다.

 

회차마다 (이전 이동 횟수의 dp값)과 (이전 이동횟수-1의 dp값 +1) 중 최댓값을 저장해준다.떨어지는 자두나무의 위치가 1이면, 0,2, ... 2n 짝수의 이동 횟수가 필요하고, 떨어지는 자두나무의 위치가 2면, 1,3,...2n-1 홀수의 이동 횟수가 필요하다.어쨋든 특정 이동 횟수 n을 기준으로 dp[t][n] = max(dp[t-1][n-1] + 1, dp[t-1][n])의 개수를 가진다.움직여서 받는 경우와 움직이지 않고 받는 경우의 최댓값을 갱신해준다.위의 로직이 끝나면, 특정 시간대의 전체 dp값을 최댓값으로 갱신한다.

 

코드

 

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

public class PlumTree_2240 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int t = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
    int[] treeArr = new int[t];
    for(int i=0; i<t; i++) {
      treeArr[i] = Integer.parseInt(br.readLine());
    }

    br.close();
    solution(treeArr, t, w);
  }

  private static void solution(int[] treeArr, int t, int w) {
    int[][] dp = new int[t+1][w+1];
    final int STANDARD = 1;

    for(int i=0; i<t; i++) { // 초
      int now = i+1;
      if(treeArr[i] == STANDARD) { // 짝수 이동 횟수 됨
        dp[now][0] = dp[i][0] +1;
        for(int j=2; j<=w; j+=2) {
          dp[now][j] = Math.max(dp[i][j-1],dp[i][j]) +1;
        }
      } else { // 홀수 이동 횟수 됨
        for(int j=1; j<=w; j+=2) {
          dp[now][j] = Math.max(dp[i][j-1],dp[i][j]) +1;
        }
      }
      for(int j=0; j<=w; j++) { // 이전 기록 저장
        dp[now][j] = Math.max(dp[i][j], dp[now][j]);
      }
    }

    int answer =0;
    for(int i=0; i<=w; i++) {
      answer = Math.max(dp[t][i], answer);
    }
    System.out.println(answer);
  }
}