[백준] BOJ_2240 - 자두나무

이종찬·2026년 2월 6일

1. 문제 정보

문제 요약: $T$ 초 동안 자두가 두 개의 나무(1번, 2번) 중 하나에서 떨어집니다. 현재 위치에서 최대 $W$ 번만 움직일 수 있을 때, 받아먹을 수 있는 자두의 최대 개수를 구하는 문제입니다. (시작 위치는 1번 나무로 고정)
난이도: Gold 5
원본 링크: https://www.acmicpc.net/problem/2240

2. 접근 방식

1) 문제의 본질: 순차적 선택과 최적 부분 구조

이 문제는 매초(1초~T초)마다 "움직일 것인가, 가만히 있을 것인가"를 선택해야 합니다. 현재의 선택이 미래의 결과에 영향을 미치고, 과거의 최적해를 이용해 현재의 최적해를 구할 수 있으므로 DP(Dynamic Programming) 가 적합합니다.

2) 알고리즘 설계: 상태 정의의 진화

단계 1: 직관적인 3차원 상태 정의

가장 먼저 떠오르는 상태 변수는 세 가지입니다.

시간 ( $t$ ): 현재 몇 초인지
이동 횟수 ( $w$ ): 지금까지 몇 번 움직였는지
현재 위치 ( $pos$ ): 1번 나무인지, 2번 나무인지

따라서 $DP[t][pos][w]$ = " $t$ 초에 $pos$ 위치에 있고, $w$ 번 움직였을 때 먹은 최대 자두 수"로 정의할 수 있습니다.

단계 2: 숨겨진 패턴 발견 (차원 축소)

여기서 논리적인 도약이 필요합니다. "현재 위치"는 독립적인 변수일까요?

자두는 1번 나무에서 시작합니다.

0번 이동 $\rightarrow$ 1번 나무
1번 이동 $\rightarrow$ 2번 나무
2번 이동 $\rightarrow$ 1번 나무
...

즉, 이동 횟수( $w$ )의 홀/짝 여부(Parity)가 곧 현재 위치를 결정합니다.

따라서 pos 차원은 불필요한 중복 정보(Redundant Information)이며, 이를 제거하여 $DP[t][w]$ 인 2차원 배열로 최적화할 수 있습니다.

3) 점화식

2차원 배열 $DP[t][w]$ 를 정의합니다.

$t$ : 현재 시간 ( $1 \dots T$ )
$w$ : 현재까지 이동한 횟수 ( $0 \dots W$ )

현재 상태( $t, w$ )에 도달하는 방법은 두 가지입니다.

가만히 있었던 경우: $t-1$ 초에 $w$ 번 이동한 상태에서 그대로 옴 ( $DP[t-1][w]$ )
방금 움직인 경우: $t-1$ 초에 $w-1$ 번 이동한 상태에서 이동함 ( $DP[t-1][w-1]$ )

이를 수식으로 표현하면 다음과 같습니다.

$DP[t][w] = \max(DP[t-1][w], DP[t-1][w-1]) + \text{Bonus}$

여기서 $\text{Bonus}$ 는 현재 위치( $w \% 2$ 로 판별)와 자두가 떨어지는 나무가 일치하면 $1$ , 아니면 $0$ 입니다.

3. 코드 구현

Approach 1: 직관적인 3차원 DP (First Draft)

위치(pos)를 명시적으로 배열 인덱스로 관리하는 방식입니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T, W;
    static int[] A;
    static int[][][] dp;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        A = new int[T + 1];
        // dp[시간][위치(1or2)][이동횟수]
        dp = new int[T + 1][3][W + 1];

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

        // 초기값 설정: 시작은 1번 나무. 
        // 0번 이동 상태에서 2번 나무에 있는 것은 불가능하므로 최소값 처리
        dp[1][2][0] = Integer.MIN_VALUE;

        for (int i = 1; i <= T; i++) {
            // 1번 나무 고정 (이동 안 함)
            dp[i][1][0] = dp[i - 1][1][0];

            // i초에 1번 나무에 있을 때의 최대 값
            for (int w = 2; w <= Math.min(i, W); w++) {
                // 이전초 2번 나무에서 이동해옴 vs 이전초 1번 나무에서 가만히 있음
                dp[i][1][w] = Math.max(dp[i - 1][2][w - 1], dp[i - 1][1][w]);
            }

            // i초에 2번 나무에 있을 때의 최대 값
            for (int w = 1; w <= Math.min(i, W); w++) {
                // 이전초 1번 나무에서 이동해옴 vs 이전초 2번 나무에서 가만히 있음
                dp[i][2][w] = Math.max(dp[i - 1][1][w - 1], dp[i - 1][2][w]);
            }

            // 현재 자두가 떨어지는 위치(p)에 따라 점수 추가
            int p = A[i];
            if (p == 1)
                dp[i][1][0] += 1;

            for (int w = 1; w <= Math.min(i, W); w++) {
                dp[i][p][w] += 1;
            }
        }

        int answer = dp[T][1][0];
        for (int i = 1; i <= W; i++) {
            int result = Math.max(dp[T][1][i], dp[T][2][i]);
            answer = Math.max(answer, result);
        }
        System.out.println(answer);
    }
}

Approach 2: 최적화된 2차원 DP

이동 횟수의 홀짝 성질을 이용하여 위치 차원을 제거한 방식입니다. 코드가 훨씬 간결해집니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T, W;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        // dp[시간][이동횟수]
        dp = new int[T + 1][W + 1];
        // 1초에 0번 이동했는데 2번 나무인 경우는 논리적 모순이므로 초기화 필요할 수 있으나,
        // 아래 로직상 j(이동횟수)가 0일 때는 current가 항상 1이므로 자연스럽게 처리됨.
        // 명시적 처리를 위해 dp[1][0] 등 초기값 설정 가능하나 여기선 루프 내 로직으로 해결.
        
        // *참고: 원본 코드의 MIN_VALUE 로직은 3차원에서 필수적이었으나, 
        // 2차원 로직에서는 current 계산에 의해 자연스럽게 점수가 안 올라가는 것으로 커버 가능.
        dp[1][0] = Integer.MIN_VALUE; // (원 코드 유지)

        for (int i = 1; i <= T; i++) {
            int now = Integer.parseInt(br.readLine()); // 자두가 떨어지는 나무

            for (int j = 0; j <= W; j++) {
                // 핵심 로직: 이동 횟수(j)가 짝수면 1번 나무, 홀수면 2번 나무
                int current = j % 2 == 0 ? 1 : 2;

                if (j > 0) {
                    // 움직여서 온 경우(j-1) vs 가만히 있었던 경우(j)
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
                } else {
                    // 이동 횟수가 0이면 무조건 가만히 있었던 경우밖에 없음
                    dp[i][j] = dp[i - 1][j];
                }

                // 자두 위치와 내 위치가 같으면 +1
                if (now == current) {
                    dp[i][j] += 1;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i <= W; i++)
            answer = Math.max(answer, dp[T][i]);

        System.out.println(answer);
    }
}

4. 회고 및 배운 점

두 풀이 모두 시간 복잡도는 $O(T \times W)$ 로 동일합니다. 하지만 공간 복잡도와 코드의 유지보수성 측면에서 2차원 배열 방식이 훨씬 우수합니다.

3차원: pos 차원을 관리하기 위해 루프가 분기되고, 초기값(Integer.MIN_VALUE) 설정 등 예외 처리가 복잡합니다.
2차원: $w \pmod 2$ 라는 간단한 연산으로 위치 정보를 복원(Restore)해냄으로써 코드가 선형적으로 깔끔해졌습니다.