[백준 2240] 자두나무(C++)

자두나무

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

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

---

문제 접근

• 각 초에 얻을 수 있는 자두의 개수를 구하는 것이 중요하다.
• 움직임의 제한이 있기 때문에 이를 풀이에 잘 반영해야 한다.
• 고려해야 할 변수는 시간, 이동한 횟수, 현재 위치하고 있는 나무의 번호이다.
• DP를 통해 각 최댓값을 구하며 진행하다가 T의 시간이 지났을 때의 최댓값을 구하면 된다.
• 1번 나무 밑에서 시작한다는 것을 잊지 말자

풀이 힌트

> 각 초마다 떨어지는 나무의 번호와 움직일 수 있는 값의 최댓값을 구하는 테이블(T[나무][움직임])를 순서대로 채워나가보자.

• 1초

현재 1번 나무에서 시작하고 2번에서 떨어지기 때문에 이동을 해서 자두를 먹거나, 이동을 하지 않고 자두를 포기한다는 두 가지 선택지가 있다.

0: 움직이지 않는 경우 0개

1: 움직이는 경우 1개

• 2초

1번 나무에서 떨어진다.

0: 움직이지 않는 경우 자두를 먹을 수 있다. 최댓값을 생각해야 하므로 움직여서 자두를 먹지 않는 경우는 생각하지 않는다.

 

 

1초에 2번 나무로 이동한 경우 다시 1번으로 움직여서 자두를 먹을 수 있다. 

1: 움직이지 않는 경우 1개가 유지된다.

2: 움직인 경우 2개로 증가한다.

※ 움직인 경우 파란색 화살표, 움직이지 않은 경우 빨간색 화살표

• 3초

1번 나무에서 떨어진다.

0: 2초에 1번 나무에서 움직이지 않은 경우 하나를 더 먹을 수 있다.

1: 2번 나무로 이동한 뒤 움직이지 않은 경우 1개가 유지된다.

2: 충돌 발생 2초에 2번 나무에서 1번 나무로 이동하여 먹는 값(1)과 1번 나무에서 움직이지 않은 값(2)를 비교한다.

    큰 값을 선택한 뒤 1을 더한 값 3개로 초기화한다.

• 4초

2번 나무에서 떨어진다.

0: 먹지 않는 경우 2개로 유지된다.

1: 충돌 발생 1번 나무에서 이동한 경우(2)와 2번 나무에서 움직이지 않은 경우(1) 중 1번 나무에서 이동한 경우(2)가 크기 때문에 1을 더하여 3으로 초기화한다. 

2: 더 이상 움직일 수 없으므로 1번 나무를 유지한다. 기존값 3 유지

• 5초

2번 나무에서 떨어진다.

0: 1번 나무에서 움직이지 않기 때문에 2 유지

1: 2번 나무에서 움직이지 않기 때문에 3에서 1개를 더해준다.

2: 1번 나무에서 움직이지 않기 때문에 3 유지

• 6초

1번 나무에서 떨어진다.

0: 1번 나무에서 움직이지 않으므로 2 + 1 = 3

1: 2번 나무에서 움직이지 않으므로 4 유지

2: 2번 나무에서 움직이지 않는 경우(3)와 1번으로 움직인 경우(4)를 비교했을 때 후자가 더 크므로 4 + 1 = 5

• 7초

1번 나무에서 떨어진다.

0: 1번 나무에서 움직이지 않으므로 3 + 1 = 4

1: 2번 나무에서 움직이지 않으므로 4 유지

2: 2번 나무에서 움직인 경우(4)와 1번 나무에서 움직이지 않은 경우(5) 중 후자가 더 크므로 5 + 1 = 6

• 최댓값 구하기

7초 대에서 얻을 수 있는 자두의 최고 값을 구하면 답을 구할 수 있다.

루트를 다시 살펴보면 아래와 같다.

구현 방법

• Table 정의

나무의 번호와 시간, 움직임을 모두 저장할 수 있는 자료형을 선언한다.

해당 시간에 어떤 나무 아래 있을 때 얻을 수 있는 자두의 최대값을 움직임 마다 저장할 테이블이다.

dp[Tree][Time][Move]

• 점화식

각 시간 각 move에 대해 올 수 있는 이전 값 중 최댓값을 찾는다.

1번 나무에서 떨어지는 경우와 2번 나무에서 떨어지는 경우를 분리하여 식을 세운다.

  1. 1번 나무에서 떨어지는 경우: [1번 나무][이전 시간][움직인 수]와 [2번 나무][이전 시간][움직인 수 - 1]를 비교하여 큰 값에 1을 더한다.

  2. 2번 나무에서 떨어지는 경우: [1번 나무][이전 시간][움직인 수 - 1]와 [2번 나무][이전 시간][움직인 수]를 비교하여 큰 값에 1을 더한다.

for (int i = 2; i <= T; ++i) {
    for (int mv = 1;  mv <= W + 1; ++mv) {
        if (tree[i] == 1) {
            dp[1][i][mv] = max(dp[1][i - 1][mv], dp[2][i - 1][mv - 1]) + 1;
            dp[2][i][mv] = max(dp[1][i - 1][mv - 1], dp[2][i - 1][mv]);
        } else {
            dp[1][i][mv] = max(dp[1][i - 1][mv], dp[2][i - 1][mv - 1]);
            dp[2][i][mv] = max(dp[1][i - 1][mv - 1], dp[2][i - 1][mv]) + 1;
        }
    }
}

• 초기값

나무 위치는 1부터 시작하기 때문에 1초에 떨어지는 나무에 따라 각 값을 초기화 한다.

※ move의 값에 1을 더해준 이유는 이후 반복문에서 이전 값을 보려고 할 때 0에 대한 예외처리를 피하기 위함이다.

if (tree[1] == 1) {
	// dp[1번 나무][1초][0번 움직임 + 1]
    dp[1][1][1] = 1;
} else {
	// dp[2번 나무][1초][1번 움직임 + 1]
    dp[2][1][2] = 1;
}

코드

#include <iostream>
#include <algorithm>

using namespace std;
/*
 * dp[Tree][Time][Move]
 */
int dp[3][1001][32];
int tree[1001];

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

    int T, W;

    cin >> T >> W;
    for (int i = 1; i <= T; ++i) {
        cin >> tree[i];
    }

    if (tree[1] == 1) {
        dp[1][1][1] = 1;
    } else {
        dp[2][1][2] = 1;
    }
    for (int i = 2; i <= T; ++i) {
        for (int mv = 1;  mv <= W + 1; ++mv) {
            if (tree[i] == 1) {
                dp[1][i][mv] = max(dp[1][i - 1][mv], dp[2][i - 1][mv - 1]) + 1;
                dp[2][i][mv] = max(dp[1][i - 1][mv - 1], dp[2][i - 1][mv]);
            } else {
                dp[1][i][mv] = max(dp[1][i - 1][mv], dp[2][i - 1][mv - 1]);
                dp[2][i][mv] = max(dp[1][i - 1][mv - 1], dp[2][i - 1][mv]) + 1;
            }
        }
    }

    int res = -1;
    for (int i = 1; i <= W + 1; ++i) {
        res = max({res, dp[1][T][i], dp[2][T][i]});
    }
    cout << res;
}

※ 오류나 개선점이 있다면 알려주세요 :) 신속히 수정하겠습니다.