이번에는 백준 4811번 알약 문제를 풀어보았습니다.
남아 있는 한 알짜리 약의 개수와 반 알짜리 약의 개수를 상태로 두고, 각 상태에서 만들 수 있는 문자열의 개수를 DP로 저장하는 방식으로 해결하였습니다.
같은 (W, H) 상태에서는 이후에 만들 수 있는 문자열의 개수가 항상 동일하므로, 재귀 + 메모이제이션을 사용하면 중복 계산을 줄일 수 있습니다.
문제 설명
처음 병에는 온전한 알약 N개가 들어 있습니다.
알약을 하나 꺼냈을 때
- 온전한 알약이라면
W - 반 조각 알약이라면
H
를 기록합니다.
온전한 알약을 꺼낸 경우에는 반으로 쪼개 한 조각을 먹고, 남은 반 조각은 다시 병에 넣습니다.
따라서 W를 선택하면
온전한 알약 -1
반 알약 +1이 됩니다.
반면 H를 선택하면 반 알약 하나를 그대로 먹으므로
반 알약 -1이 됩니다.
총 2N일 동안 만들 수 있는 서로 다른 문자열의 개수를 구하는 문제입니다.
풀이 아이디어
DP 상태를 다음과 같이 정의하였습니다.
DP[W][H]W: 현재 남아 있는 온전한 알약의 개수H: 현재 남아 있는 반 알약의 개수
현재 상태에서 가능한 선택은 두 가지입니다.
1. 온전한 알약을 먹는 경우
온전한 알약이 하나 이상 남아 있다면 W를 기록할 수 있습니다.
이 경우
W → W - 1
H → H + 1이므로 다음 상태는
solve(W-1, H+1)이 됩니다.
2. 반 알약을 먹는 경우
반 알약이 하나 이상 남아 있다면 H를 기록할 수 있습니다.
이 경우
H → H - 1이므로 다음 상태는
solve(W, H-1)이 됩니다.
두 경우의 수를 더하면 현재 상태에서 만들 수 있는 모든 문자열의 개수가 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
long long DP[31][31];
int type[2];
int N;
long long solve(int W, int H) {
if (W == 0 && H == 0) return 1;
if (DP[W][H]) return DP[W][H];
long long int &ret = DP[W][H];
if (W > 0) ret += solve(W-1, H+1);
if (H > 0) ret += solve(W, H-1);
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
while(true) {
int n;
cin >> n;
if (n == 0) break;
cout << solve(n, 0) << '\n';
}
return 0;
}풀이 흐름
- 처음에는 온전한 알약
N개, 반 알약0개에서 시작합니다.
solve(n, 0)- 현재 온전한 알약이 남아 있다면 하나를 꺼내 반으로 나눕니다.
solve(W-1, H+1)- 현재 반 알약이 남아 있다면 하나를 먹습니다.
solve(W, H-1)-
두 선택에서 나오는 문자열의 개수를 모두 더합니다.
-
동일한
(W, H)상태가 다시 등장하면DP[W][H]에 저장되어 있던 값을 재사용합니다. -
온전한 알약과 반 알약이 모두 0개가 되었다면 하나의 완성된 문자열을 만든 것이므로
1을 반환합니다.
구현 포인트
1. DP 상태
long long DP[31][31];DP[W][H]는
온전한 알약이 W개,
반 알약이 H개 남아 있을 때
앞으로 만들 수 있는 문자열의 개수를 의미합니다.
문제에서 N ≤ 30이므로 각 개수는 최대 30까지 관리하면 됩니다.
2. 시작 상태
처음 병에는 온전한 알약만 N개 들어 있습니다.
따라서 시작 상태는
solve(n, 0)입니다.
즉,
W = N
H = 0에서 출발합니다.
3. 온전한 알약을 선택하는 경우
if (W > 0) ret += solve(W-1, H+1);온전한 알약을 꺼내면 문자 W가 기록됩니다.
그 알약은 반으로 나뉘고
- 한 조각은 먹음
- 남은 한 조각은 병으로 돌아감
따라서 상태는
(W, H)
→
(W-1, H+1)로 변경됩니다.
4. 반 알약을 선택하는 경우
if (H > 0) ret += solve(W, H-1);반 알약을 꺼내면 문자 H가 기록됩니다.
반 알약은 바로 먹으므로 병에서 하나가 사라집니다.
따라서 상태는
(W, H)
→
(W, H-1)가 됩니다.
5. 두 경우의 수를 더하는 이유
현재 상태에서 첫 번째 문자는
W 또는 H가 될 수 있습니다.
두 경우는 서로 다른 문자열을 만들기 때문에 경우의 수를 더하면 됩니다.
if (W > 0) ret += solve(W-1, H+1);
if (H > 0) ret += solve(W, H-1);즉, 점화식은 다음과 같이 볼 수 있습니다.
DP[W][H]
=
DP[W-1][H+1]
+
DP[W][H-1]단, 실제로 해당 약이 존재하는 경우에만 계산합니다.
6. 종료 조건
if (W == 0 && H == 0) return 1;온전한 알약과 반 알약이 모두 사라졌다면 모든 약을 먹은 상태입니다.
즉, 길이 2N의 문자열 하나가 완성된 것이므로 경우의 수 1을 반환합니다.
7. 메모이제이션
if (DP[W][H]) return DP[W][H];같은 (W, H) 상태에 도달했다면 이후 가능한 선택은 완전히 동일합니다.
따라서 이전에 계산했던 값이 있다면 다시 재귀를 돌리지 않고 바로 반환합니다.
이 방식으로 중복 계산을 크게 줄일 수 있습니다.
8. 참조 변수 사용
long long int &ret = DP[W][H];현재 DP 상태를 참조 변수 ret으로 받아 사용하였습니다.
따라서
ret += ...을 수행하면 바로
DP[W][H]에 값이 저장됩니다.
9. 여러 테스트 케이스에서 DP 재사용
입력은 최대 1000개의 테스트 케이스로 이루어져 있습니다.
하지만
DP[W][H]의 값은 어떤 테스트 케이스에서 호출하든 동일합니다.
예를 들어
DP[5][3]은 언제 계산하더라도 같은 값을 가지므로, 한 번 계산해두면 다음 테스트 케이스에서도 그대로 사용할 수 있습니다.
따라서 테스트 케이스마다 DP를 초기화하지 않고 계속 재사용할 수 있습니다.
10. long long 사용
경우의 수는 빠르게 증가합니다.
N이 최대 30일 때 결과가 int 범위를 넘어갈 수 있으므로
long long DP[31][31];로 선언하였습니다.
재귀 함수의 반환형 역시
long long solve(int W, int H)으로 설정하였습니다.
시간복잡도
DP 상태는
W : 0 ~ 30
H : 0 ~ 30이므로 가능한 상태의 개수는 대략
O(N²)입니다.
각 상태에서는 최대 두 개의 다음 상태만 확인합니다.
따라서 전체 시간복잡도는
O(N²)입니다.
여러 테스트 케이스가 들어오더라도 이미 계산된 DP 값은 그대로 재사용하므로 매우 빠르게 처리할 수 있습니다.
공간복잡도 역시
O(N²)입니다.
