[PS][DP] BOJ 9764 : 서로 다른 자연수의 합

[2021년 08월 09일 19시 33분 작성]

[PS][DP]
BOJ 9764 : 서로 다른 자연수의 합

---

[문제 링크 : 클릭]

---

1. 풀이

 

문제를 조금 다르게 풀었습니다.

 

"주어진 자연수 k를 서로 다른 여러 자연수를 빼서 0을 만들때, 총 몇 가지의 방법이 나오는가?"

 

DP(k, n) --> k를 0으로 만드는 방법의 수 (이전 분기에서 마지막으로 사용된 수는 n)

 

위 함수 정의를 기반으로 코드를 전개해주면 해결이 가능합니다.

 

 

+) MOD 연산을 각 분기마다 추가해주어 문제의 조건에 맞추도록 합니다.

---

2. 소스코드

[Github 링크 : 클릭]

#include <bits/stdc++.h>
using namespace std;

const int INF = 100999;

int n;
int cache[2001][2001];

//k를 0으로 만드는 방법의 수 (마지막으로 사용한 수가 curr)
int GetAnswer(int k, int curr)
{
	if(k==0) return 1; //기저사례 : 0을 만들 수 있다면, 방법을 하나 찾음

	int &ret = cache[k][curr];
	if(ret != 0) return ret; //메모이제이션

	for(int i=curr+1; i<=k; i++) //중복 사용 방지 : 마지막으로 사용한 수+1 ~ k를 이용 
		ret = (GetAnswer(k-i, i)+ret)%INF;

	return ret%INF;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int t;
	cin>>t;

	while(t--)
	{
		cin>>n;
		cout<<GetAnswer(n, 0)<<'\n';
	}

	return 0;
}

---

3. 복기

- Bottom Up으로 해결하면, 시간&공간적으로 절약이 가능할 듯