백준 2240번 [자두나무](C++) -yes6686- 티스토리

백준 문제 풀이: 2240 [자두나무]

---

문제 링크: https://www.acmicpc.net/problem/2240

문제 설명:

자두나무 두 그루가 있고, 매초마다 1번 또는 2번 나무에서 자두가 떨어집니다. 자두를 받으려면 특정 나무 아래 있어야 하며, 최대 W번 다른 나무로 이동할 수 있습니다. T초 동안 받을 수 있는 최대 자두의 개수를 계산하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001];           // 자두가 떨어지는 나무 정보
int dp[1001][31][3];     // dp[t][w][pos]: t초에 w번 이동 후 pos 나무 아래에 있을 때 최대 자두 개수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T, W; // 총 시간 T, 최대 이동 횟수 W
    cin >> T >> W;

    for (int i = 0; i < T; i++) {
        cin >> arr[i];
    }

    // DP 배열 초기화
    for (int i = 0; i < T; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j][1] = dp[i][j][2] = -1;
        }
    }

    // 초기 상태
    dp[0][0][1] = (arr[0] == 1) ? 1 : 0;
    dp[0][1][2] = (arr[0] == 2) ? 1 : 0;

    int maxAns = max(dp[0][0][1], dp[0][1][2]);

    // DP 계산
    for (int i = 1; i < T; i++) {
        for (int j = 0; j <= W; j++) {
            // 현재 나무가 1번일 때
            if (arr[i] == 1) {
                if (dp[i - 1][j][1] != -1) dp[i][j][1] = dp[i - 1][j][1] + 1; // 이동 없이 자두 받음
                if (j > 0 && dp[i - 1][j - 1][2] != -1) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][2] + 1); // 2번에서 이동 후 받음
                if (dp[i - 1][j][2] != -1) dp[i][j][2] = dp[i - 1][j][2]; // 2번에 계속 머무름
            } else { // 현재 나무가 2번일 때
                if (dp[i - 1][j][2] != -1) dp[i][j][2] = dp[i - 1][j][2] + 1; // 이동 없이 자두 받음
                if (j > 0 && dp[i - 1][j - 1][1] != -1) dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j - 1][1] + 1); // 1번에서 이동 후 받음
                if (dp[i - 1][j][1] != -1) dp[i][j][1] = dp[i - 1][j][1]; // 1번에 계속 머무름
            }
        }
    }

    // 최대 자두 개수 계산
    for (int j = 0; j <= W; j++) {
        maxAns = max({maxAns, dp[T - 1][j][1], dp[T - 1][j][2]});
    }

    cout << maxAns << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍으로 현재 상태(시간, 이동 횟수, 위치)를 기반으로 최대 자두 개수를 계산합니다.
• 구현 세부사항:
  • dp[t][w][pos]: t초에 w번 이동 후 pos 나무 아래에 있을 때 받을 수 있는 최대 자두 개수
  • 점화식:
    • 현재 자두가 떨어지는 나무 아래 있으면 +1
    • 이동하거나 이동하지 않고 받는 경우 중 최댓값
• 시간 복잡도 분석: O(T × W)
  • 시간 T에 대해 최대 이동 W와 두 나무 상태를 계산

---

결과

주어진 조건을 만족하며 받을 수 있는 자두의 최대 개수를 정확히 계산합니다. DP 배열로 각 상태를 추적하며 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!