이번에는 백준 2240번 자두나무 문제를 풀어보았습니다.
매 초 1번 또는 2번 나무에서 자두가 떨어지고, 자두는 처음에 1번 나무 아래에서 시작합니다. 최대 W번까지만 나무 사이를 이동할 수 있으므로, 각 시간마다 현재 나무에 그대로 있을지, 반대편 나무로 이동할지를 선택해야 합니다.
dp[시간][현재 나무][남은 이동 횟수] 형태로 상태를 구성하고, 재귀와 메모이제이션을 이용하여 받을 수 있는 자두의 최대 개수를 구하였습니다.
문제 설명
총 T초 동안 매 초마다 1번 또는 2번 나무에서 자두가 하나씩 떨어집니다.
자두는 처음에 1번 나무 아래에 있으며, 두 나무 사이를 최대 W번 이동할 수 있습니다.
각 시간마다 현재 서 있는 나무에서 자두가 떨어진다면 해당 자두를 먹을 수 있습니다.
따라서 제한된 이동 횟수 안에서 적절하게 나무를 이동하며 먹을 수 있는 자두의 최대 개수를 구해야 합니다.
풀이 아이디어
DP를 다음과 같이 구성하였습니다.
dp[idx][tree][cnt]각 값의 의미는 다음과 같습니다.
idx : 현재 몇 번째 자두를 확인하고 있는지
tree : 현재 어느 나무 아래에 서 있는지
cnt : 앞으로 움직일 수 있는 남은 횟수코드에서는 나무를 0, 1로 관리합니다.
tree = 0 → 1번 나무
tree = 1 → 2번 나무현재 상태 (idx, tree, cnt)에서는 두 가지 선택을 할 수 있습니다.
1. 현재 나무에 그대로 있는다.
2. 반대쪽 나무로 이동한다.그대로 있는 경우에는 이동 횟수가 줄어들지 않으므로
solve(idx+1, tree, cnt)가 됩니다.
반대편 나무로 이동한다면 이동 횟수를 하나 사용하므로
solve(idx+1, tree^1, cnt-1)가 됩니다.
두 경우 중 더 큰 값을 선택하여 현재 상태의 최댓값을 구합니다.
코드
#include <bits/stdc++.h>
using namespace std;
int T,W, dp[1000][2][31];
int arr[1000];
int solve(int idx, int tree, int cnt) {
if (cnt < 0) return -1e9;
if (idx == T) return 0;
int &ret = dp[idx][tree][cnt];
if (ret != -1) return ret;
return ret = max(solve(idx+1, tree, cnt), solve(idx+1, tree^1, cnt-1)) + (tree == arr[idx]-1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T >> W;
memset(dp, -1, sizeof(dp));
for (int i=0; i<T; i++) {
cin >> arr[i];
}
int ret = max(solve(0,0,W),solve(0, 1, W-1));
cout << ret;
return 0;
}풀이 흐름
-
T,W를 입력받고 각 시간에 자두가 떨어지는 나무를arr에 저장합니다. -
dp배열을-1로 초기화합니다. -
solve(idx, tree, cnt)를 통해 현재 시간, 현재 나무, 남은 이동 횟수를 상태로 관리합니다. -
현재 나무에 계속 있는 경우와 반대쪽 나무로 이동하는 경우를 모두 확인합니다.
-
두 경우 중 더 많은 자두를 받을 수 있는 경우를 선택합니다.
-
현재 위치와 이번에 자두가 떨어지는 나무가 같다면
1을 더합니다. -
계산한 결과는
dp에 저장하여 같은 상태를 다시 계산하지 않습니다. -
처음부터 1번 나무에 있는 경우와 시작 전에 2번 나무로 한 번 이동한 경우를 각각 계산합니다.
-
두 값 중 큰 값을 출력합니다.
구현 포인트
1. DP 상태 구성
int T,W, dp[1000][2][31];DP의 상태를 세 가지 정보로 구성하였습니다.
dp[idx][tree][cnt]idx는 현재 시간, tree는 현재 위치한 나무, cnt는 남아 있는 이동 가능 횟수를 의미합니다.
예를 들어
dp[10][0][5]라면 10번째 상태에서 현재 1번 나무 아래에 있고, 앞으로 5번 더 이동할 수 있는 상태에서 얻을 수 있는 최대 자두 개수를 의미합니다.
시간만으로는 현재 어느 나무에 있는지 알 수 없고, 현재 나무만으로는 앞으로 몇 번 이동할 수 있는지 알 수 없으므로 세 정보를 모두 DP 상태에 포함해야 합니다.
2. tree를 0과 1로 관리
입력에서는 나무의 번호가 1, 2로 주어집니다.
하지만 코드에서는
0 → 1번 나무
1 → 2번 나무로 관리합니다.
따라서 현재 떨어지는 자두와 위치를 비교할 때는
tree == arr[idx]-1을 사용합니다.
arr[idx]가 1이라면 arr[idx]-1은 0이고, arr[idx]가 2라면 1이 됩니다.
3. 현재 위치에 그대로 있는 경우
현재 위치에서 움직이지 않는다면 다음 시간에도 같은 나무에 있습니다.
solve(idx+1, tree, cnt)시간만 하나 증가하고, 나무와 남은 이동 횟수는 그대로 유지됩니다.
즉,
(idx, tree, cnt)
↓
(idx + 1, tree, cnt)가 됩니다.
4. 반대쪽 나무로 이동하는 경우
solve(idx+1, tree^1, cnt-1)다른 나무로 이동한다면 이동 가능 횟수를 하나 사용합니다.
따라서 cnt-1을 전달합니다.
또한 현재 나무를 반대편으로 바꾸기 위해
tree^1을 사용하였습니다.
tree는 0 또는 1만 가지므로 XOR 연산을 사용하면
0 ^ 1 = 1
1 ^ 1 = 0이 됩니다.
따라서 간단하게 반대편 나무를 표현할 수 있습니다.
5. 두 선택 중 최댓값 구하기
max(solve(idx+1, tree, cnt), solve(idx+1, tree^1, cnt-1))현재 상태에서는
그대로 있기
이동하기두 가지 선택이 가능합니다.
문제에서는 먹을 수 있는 자두의 최대 개수를 구해야 하므로 두 경우의 결과 중 큰 값을 선택합니다.
이러한 선택을 모든 시간에 대해 반복하면서 최적의 이동 경로를 찾게 됩니다.
6. 현재 자두를 먹을 수 있는지 확인
(tree == arr[idx]-1)C++에서 비교 연산의 결과는 참이면 1, 거짓이면 0입니다.
따라서 현재 위치와 자두가 떨어지는 나무가 같다면
1이 더해지고, 다르다면
0이 더해집니다.
전체 점화식은 다음 코드 한 줄로 구성됩니다.
return ret = max(solve(idx+1, tree, cnt), solve(idx+1, tree^1, cnt-1)) + (tree == arr[idx]-1);즉,
현재 위치에서 자두를 먹었는가
+
이후 시간에서 얻을 수 있는 최대 자두 개수를 계산합니다.
7. 현재 자두를 먼저 계산하는 구조
코드에서 한 가지 확인해야 할 부분은 tree가 현재 idx번째 자두가 떨어지는 순간의 위치를 의미한다는 점입니다.
(tree == arr[idx]-1)로 현재 자두를 먹었는지 확인한 뒤,
solve(idx+1, tree, cnt)
solve(idx+1, tree^1, cnt-1)를 통해 다음 시간의 위치를 결정합니다.
즉, 재귀 호출에서 나무를 변경하는 것은 다음 자두가 떨어지기 전까지 이동하는 것으로 볼 수 있습니다.
8. 이동 횟수를 모두 사용한 경우
cnt == 0이라고 해서 바로 종료되는 것은 아닙니다.
더 이상 이동할 수 없을 뿐, 현재 나무에 계속 서 있으면서 이후에 떨어지는 자두를 받을 수 있기 때문입니다.
따라서 cnt == 0인 상태에서도
solve(idx+1, tree, cnt)는 계속 진행됩니다.
반면 이동하는 경우에는
solve(idx+1, tree^1, cnt-1)가 되어 cnt가 -1이 됩니다.
이를 다음 조건으로 막습니다.
if (cnt < 0) return -1e9;9. cnt가 음수가 된 경우
if (cnt < 0) return -1e9;남은 이동 횟수가 없는 상태에서 또 이동하는 것은 불가능한 경우입니다.
이러한 경우가 max()에서 선택되지 않도록 매우 작은 값인 -1e9를 반환합니다.
단순히 0을 반환하면 잘못된 이동을 한 경우가 정상적인 경로처럼 비교될 가능성이 있으므로, 절대 선택되지 않을 정도로 작은 값을 반환합니다.
10. 모든 시간을 확인한 경우
if (idx == T) return 0;idx == T라면 0번부터 T-1번까지 모든 자두를 확인한 상태입니다.
더 이상 받을 수 있는 자두가 없으므로 0을 반환하면서 재귀를 종료합니다.
11. 메모이제이션
int &ret = dp[idx][tree][cnt];
if (ret != -1) return ret;같은 idx, tree, cnt 상태에 도달했다면 이후에 할 수 있는 선택은 항상 동일합니다.
따라서 한 번 계산한 결과를 dp에 저장해 두었다가 같은 상태에 다시 도착하면 바로 반환합니다.
int &ret = dp[idx][tree][cnt];처럼 참조 변수로 선언했기 때문에 이후
return ret = ...으로 계산 결과를 바로 해당 DP 칸에 저장할 수 있습니다.
12. dp를 -1로 초기화
memset(dp, -1, sizeof(dp));DP 배열에서 -1은 아직 계산하지 않은 상태를 의미합니다.
실제로 받을 수 있는 자두의 개수는 최소 0이므로 -1을 미계산 상태로 사용하는 데 문제가 없습니다.
따라서
if (ret != -1) return ret;을 통해 이미 계산된 상태인지 판단할 수 있습니다.
13. 시작 상태를 두 가지로 확인하는 이유
문제에서 자두는 처음에 1번 나무 아래에 있습니다.
따라서 이동하지 않고 시작한다면
solve(0,0,W)가 됩니다.
tree = 0이므로 첫 번째 자두가 떨어질 때 1번 나무에 있는 상태입니다.
하지만 첫 번째 자두가 떨어지기 전에 바로 2번 나무로 이동하는 선택도 가능합니다.
이 경우 처음부터 이동 횟수를 하나 사용했으므로
solve(0,1,W-1)이 됩니다.
따라서 최종적으로
int ret = max(solve(0,0,W),solve(0, 1, W-1));두 경우를 비교합니다.
14. 첫 번째 자두가 2번 나무에서 떨어지는 경우
예를 들어 첫 번째 입력이
2라고 하겠습니다.
첫 번째 경우인
solve(0, 0, W)에서는 1번 나무에 있으므로 첫 번째 자두를 먹지 못합니다.
반면
solve(0, 1, W-1)에서는 시작 전에 한 번 이동하여 2번 나무에 있으므로 첫 번째 자두를 먹을 수 있습니다.
이처럼 시작 상태를 두 개 확인함으로써 첫 번째 자두가 떨어지기 전에 이동하는 경우까지 포함할 수 있습니다.
15. 전체 DP 구조
전체적인 상태 전이는 다음과 같습니다.
dp[idx][tree][cnt]
│
├── 이동하지 않음
│
└── dp[idx+1][tree][cnt]
│
└── 반대쪽으로 이동
└── dp[idx+1][tree^1][cnt-1]그리고 두 결과 중 큰 값에
현재 tree에서 자두를 먹었다면 +1을 해줍니다.
즉, 현재 위치와 남은 이동 횟수만 알고 있다면 이후의 최적 결과를 계산할 수 있으므로 DP로 해결할 수 있습니다.
시간복잡도
DP의 상태는
시간 : 최대 T
나무 : 2개
남은 이동 횟수 : 최대 W + 1개이므로 전체 상태의 개수는
T × 2 × (W + 1)정도입니다.
각 상태에서는 이동하지 않는 경우와 이동하는 경우 두 개만 확인하므로 전체 시간복잡도는
O(T × W)입니다.
T ≤ 1,000, W ≤ 30이므로 충분히 빠르게 해결할 수 있습니다.
dp 배열이 대부분의 공간을 차지하므로 공간복잡도 역시
O(T × W)입니다.
