문제 이해 단계
입력으로 N 개의 숫자들이 하나씩 띄어져서 주어진다.
마지막 수 앞에는 무조건 등호(=)가 들어가고
맨 앞을 제외하고는 +나 -를 자유롭게 넣을 수 있다.
여기서 조건이 하나 주어지는데,
중간 계산 가운데에 연산 값이 0 ~ 20 사이여야 한다.
즉 음수가 나오거나 20이 넘어가면 안 된다는 점을 유의해야 한다.
이러한 조건에서 수식을 올바르게 일치시키는
경우의 수를 구하는 문제이다.
힌트를 보면 대충 무슨 소리인지 이해가 될 것이다.
문제 접근 단계
힌트라고 주긴 줬는데,
솔직히 매직아이 올 거 같아서 힌트는 생각 안 하는 게 나을 것 같다.
위의 예제들로 생각해 보자.
위에 숫자들이 너무 많은데
8이 나오도록 끝에서부터 계산한다고 생각해 보자.
8 3 2 4 8 7 2 4 0 8 = 8
이를 +-연산에 의해 8을 만들어야 한다.
이를 두 개의 묶음으로 나눠보자.
(8 3 2 4 8 7 2 4 0) 8 = 8
이렇게 될 건데,
이때 왼쪽에 혼자 있는 8 앞에는 +나 - 둘 다 붙을 수 있다.
(8 3 2 4 8 7 2 4 0) + 8 = 8
(8 3 2 4 8 7 2 4 0) - 8 = 8
이렇게 두 가지의 경우의 수가 나올 것이다.
이를 이항하고 정리해 보면
(8 3 2 4 8 7 2 4 0) = 0
(8 3 2 4 8 7 2 4 0) = 16
한번 더 가보겠다.
다시 한번 두 묶음으로 분리해서 계산해 보겠다.
(8 3 8 2 4 8 7 2 4) + 0 = 0
(8 3 8 2 4 8 7 2 4) - 0 = 16
0 또한 앞에 +와 -를 붙일 수 있으므로
의미는 크게 없지만 이런 식으로 쓸 순 있다.
이를 다시 정리하면
(8 3 8 2 4 8 7 2 4) = 0
(8 3 8 2 4 8 7 2 4) = 16
이렇게 첫 번째 숫자까지 반복하면
모든 경우의 수를 쉽게 구할 수 있을 수 있을 것이다.
이는 하나의 경우의 수가
다른 경우의 수를 계속해서 반복하는 것이기 때문에 재귀함수로 구현이 가능하다.
그리고 여기서 변하는 것은 괄호로 된 N의 개수와 합의 값이기 때문에
이를 DP의 변수로 사용했다.
DP [a][b] = c : 숫자의 개수가 a개이고 합의 결과가 b일 때의 경우의 수는 c
예를 들어 (8 3 2 4 8 7 2 4 0)=16 = DP [9][16]이다.
이를 이용하여 재귀함수를 구현할 건데,
유의해야 할 점은 항상 계산할 때 합이 0~20을 벗어나면 안 된다는 점이다.
그리고 첫 번째 숫자까지 갔을 때의 숫자가
합의 결과와 같아야만 올바른 수식이라고 볼 수 있다.
자세한 것은 코드로 살펴보겠다.
문제 구현 단계
int num[101];
long long d[101][21];
long long Dp(int x, int y){
if(x < 1 || y > 20 || y < 0) return 0;
if(x == 1){
if(num[x] == y) return 1;
else return 0;
}
if(d[x][y] != 0) return d[x][y];
long long count = 0;
count += Dp(x-1,y+num[x]);
count += Dp(x-1,y-num[x]);
return d[x][y] = count;
}핵심이 되는 DP함수이다. 매개변수로 인덱스 x와 합의 값 y를 받는다.
2^63-1까지 가능하기 때문에 long long으로 선언해 줬다.
초반 설정으로 계산 중간에 y 값이 1~20을 벗어나지 않고,
x도 1 아래로 떨어지지 않도록 설정했다.
그리고 첫 번째 번호에 왔을 때,
y값과 같을 때만 올바른 수식임을 인식한다.
그 밑에 것은 두 가지 +-의 DP를 모두 호출하고 그 경우의 수를 반환한다.
설명은 여기서 끝이고 아래는 전체 함수를 올리고 끝내겠다.
#include <iostream>
using namespace std;
int num[101];
long long d[101][21];
long long Dp(int x, int y){
if(x < 1 || y > 20 || y < 0) return 0;
if(x == 1){
if(num[x] == y) return 1;
else return 0;
}
if(d[x][y] != 0) return d[x][y];
long long count = 0;
count += Dp(x-1,y+num[x]);
count += Dp(x-1,y-num[x]);
return d[x][y] = count;
}
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
int N;
cin >> N;
for(int i = 1; i <= N; i++) cin >> num[i];
long long ans = 0;
ans = Dp(N-1,num[N]);
cout << ans;
}
시행착오
첫 접근이 좀 걸렸던 것 같다.
이는 Top-Down 방식으로 풀었는데, DP를 오랜만에 재귀함수 방식으로 풀어봤던 것 같다.
처음에는 힌트 때문에 오히려 헷갈려서 너무 막막했는데
두 가지 묶음으로 나누는 방법을 생각하니까
그 뒤로는 로직 짜는 것에 대해 막히는 것은 없었다.
그 뒤에 구현에서 DP를 어떤 걸로 설정하느냐에서 좀 걸렸던 것 같다.
처음에는 두 가지 경우의 수로 안 나뉘니까
0,1 두 개로밖에 안 나눴는데, 0~20으로 나눠야 한다는 것을 나중에야 알았다.
근데 이러면 왜 DP지? 아직 와닿지는 않는다.
아직 공부가 더 필요하긴 할 거 같다.