[BOJ] 백준 2240 - 자두나무 풀이

1. 문제

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

2240번: 자두나무

2. 풀이

• 자두는 현재 1번 자두나무 아래에 위치해있다.
• 1번 움직인다면 2번 자두나무 아래에 위치하고, 2번 움직이면 1번 자두나무 아래에 위치할 것이다.
• 이를 일반화한다면 다음과 같다.
  • 짝수번 움직일 경우 : 1번 자두나무
  • 홀수번 움직일 경우 : 2번 자두나무
• 입력으로 자두가 떨어지는 자두나무의 번호가 주어질 때 나올 수 경우의 수는 어떻게 될까??
  1. 내가 짝수번 움직였을 때 떨어지는 자두의 나무 번호가 1일 때 OR 내가 홀수번 움직였을 때 떨어지는 자두의 나무 번호가 2일 때.
     • 이때는 움직이지 않으면 자두를 먹을 수 있기 때문에 "짝수번 움직였을 때 이전 자두까지 떨어졌을 때의 최대 먹을 수 있는 자두의 개수" + 1을 할 수 있다.
  2. 내가 짝수번 움직였을 때 떨어지는 자두의 나무 번호가 2일 때 OR 내가 홀수번 움직였을 때 떨어지는 자두의 나무 번호가 1일 때.
     
     • 이때는 (1) 움직이지 않았을 때 이전 자두까지 떨어졌을 때의 최대 먹을 수 있는 자두의 개수와 (2) 짝수면 홀수, 홀수면 짝수번 움직였을 때 이전 자두까지 떨어졌을 때의 최대 먹을 수 있는 자두의 개수 + 1 중 최대를 구해야 한다.
• 이를 DP 식으로 나타내면 다음과 같다.

dp[m][k] = r
내가 m번 움직였고 k개의 자두가 떨어졌을 때 최대 먹을 수 있는 자두의 개수 = r

1. 내가 짝수번 움직였을 때 떨어지는 자두의 나무 번호가 1일 때 OR 내가 홀수번 움직였을 때 떨어지는 자두의 나무 번호가 2일 때.
   • dp[i][j] = dp[i][j - 1] + 1
2. 내가 짝수번 움직였을 때 떨어지는 자두의 나무 번호가 2일 때 OR 내가 홀수번 움직였을 때 떨어지는 자두의 나무 번호가 1일 때.
   • dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - 1] + 1)
     
     
     

3. 소스 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] jaduArr = new int[T + 1];
        for (int i = 1; i <= T; i++) {
            jaduArr[i] = Integer.parseInt(br.readLine());
        }
        int result = Integer.MIN_VALUE;

        int[][] dp = new int[W + 1][T + 1];
        for (int i = 1; i <= T; i++) {
            if (jaduArr[i] == 1) {
                dp[0][i] = dp[0][i - 1] + 1;
                result = Math.max(result, dp[0][i]);
            }
        }

        // 처음에 1번에 있으므로 홀수번 움직였다면 2번에 있고 짝수번 움직였다면 1번에 있을 것이다.
        for (int i = 1; i <= W; i++) {
            for (int j = 1; j <= T; j++) {
                // 짝수번 움직였다면 1번 사과를 먹을 것이다.
                if ((i % 2 == 0 && jaduArr[j] == 1) || (i % 2 == 1 && jaduArr[j] == 2)) {
                    dp[i][j] = dp[i][j - 1] + 1;
                } else if ((i % 2 == 0 && jaduArr[j] == 2) || (i % 2 == 1 && jaduArr[j] == 1)) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - 1] + 1);
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
                result = Math.max(result, dp[i][j]);
            }
        }
        
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

4. 점수

80 / 100