결론
기저사례 작성시, 실패와 성공 사례를 함께 작성하자.
그런데 경우의 수 문제 재귀함수 옆에 카운팅하는
탑다운은 반드시 조건처리해야 한다.
혹시 모를 바텀업 변겨을 위해 누적이 아닌 차감하는 방식으로 코드 작성하자.
시간복잡도는
-
재귀형식이기 하지만, 탑다운 코드에서 중복처리되므로,
다른 시점에서 시간복잡도를 계산해야 한다. -
지금의 경우, k값까지 진행하고, idx가 n만큼 진행하는 것이 기준이므로
-> k * N만큼의 시간복잡도가 발생한다.
-함수내의 호출로 시간복잡도를 생각하면 안됨
탑다운도 가능하다.
-
내가 틀린 이유는 기저사례를 성공조건만 작성했기 때문이다.
-
정답코드
#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <string>
using namespace std;
int memo[101][10001]; // 적절한 크기
vector<int> v;
int n, k;
int go(int idx, int ssum) {
if (ssum == k) return 1; // 정확히 목표 도달
if (ssum > k || idx == n) return 0; // 초과하거나 동전 다 씀
int& ret = memo[idx][ssum];
if (ret != -1) return ret; // 이미 계산함
// 1. 현재 동전을 사용 (idx를 유지하여 또 사용할 수 있게 함)
ret = go(idx, ssum + v[idx]);
// 2. 현재 동전을 더 이상 사용하지 않음
ret += go(idx + 1, ssum);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
v.resize(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
// DP 배열 초기화
memset(memo, -1, sizeof(memo));
// 0번째 동전부터, 현재 금액 0으로 시작
cout << go(0, 0) << "\n";
return 0;
}
바텀업과의 동일시를 위해
-
차감하는 식으로 하자.
-
그래야 추후에 바텀업 전환시 쉽게 변경이 가능하다.
: 바텀업은 낮은 인덱스를 가지고 와서 사용하므로 누적 불가
문제 해결 전략
-
탑다운으로 하기에는 문제에서 경우의 수가 2의 30승이라고 하므로, ,, 또는 n이 100이므로, 2의 100승이다.
-
k값이 10000만이고, 모든 원소가 전부 1이라고 하는 경우,
- 어쨋든 탑다운 코드를 임시로 작성함.
바텀업으로 하기로 했으니,
-> 점화식을 반드시 작성해야 함.
-
표를 만들기로 했다.
-
1) 1번 값을 가지고 10을 만들수 있는 경우의 수 는 이렇다.
-
2) 2번 을 가지고 10을 만드는 경우의 수는
-
일단 2번값을 가지고 1을 만들수 는 없다.
-> 결론 : 점화식을 이렇게 작성할 수 있다.
memo[x] : 문제에서 주어진 값을 가지고 x를 만들수 있는 경우의 수
-
다시 2번으로 돌아와서 인덱스 오름차순으로 이렇게 메모이제이션을 작성해야 겠다 판단함.
-
3) 초기값 memo[x] : x를 만드는 경우의 수인데,
memo[0] 은 어떻게 표현할까?
0을 만드는 경우의 수는 모두 선택하지 않는 1개가 있다.
다시 탑다운 코드를 보면.
-
가) 이 코드를 어떻게 for문으로 표현할까? 가 관건이다.
-
결론) 첫번재 for 표현
: 인덱스 그대로 하면서 증가하는 go 함수와 , 인덱스만 증가하는 go함수를 나타냈기 때문에 for문으로 이렇게 표현이 가능하다.
-> i가 1이 되면, 0번 인덱스를 제외한 상태에서 진행한다.
-
나) 이 조건식을 어떻게 표현할수 있을까? 인데 ,
-
여기서는 위에서 발견한 점화식과 함께 결합해야 한다.
점화식은 memo[x] = memo[x] + memo[x - target] 이다.
-
일단 작성하자.
-
j를 어떻게 작성할까? 인데, 여기서는 점화식의 모든 k값까지 진행해야 함.
: 여기서는 점화식을 표현하려는 느낌이 강하고, -
탑다운의 더하는 것과 조건식을 반대로 작성해야 한다.
-> 왜냐하면 바텀업은 자신보다 낮은 인덱스를 가지고 진행하므로
-
결론
-> 이렇게 작성함.
: 탑다운 코드를 보면, 선택하지 않은거과 선택한 거를 그대로 가지고 온 것이고, 점화식과 동일한 것을 확인할 수 있다.
