5557번 - 1학년
#include<iostream>using namespace std;
int N;int nums[100];int DP[100][21];int target; int Calc(int pos,int sum){ //base-case판단 if (pos == N - 1 && sum == target) return (sum == target) ? 1 : 0;
if (DP[pos][sum] != -1) return DP[pos][sum]; int ret = 0;
if (sum + nums[pos] <= 20) ret += Calc(pos + 1, sum + nums[pos]); if (sum - nums[pos] >= 0 ) ret += Calc(pos + 1, sum - nums[pos]); DP[pos][sum] = ret; return DP[pos][sum];}int main(){ int cases; //입력 cin >> N; for (int i = 0; i < N; i++) cin >> nums[i]; //초기화 for (int i = 0; i < N; i++) for (int j = 0; j < 21; j++) DP[i][j] = -1;
target = nums[N - 1]; cases=Calc(1, nums[0]); cout << cases << endl; return 0;}
if (pos == N - 1 && sum == target) return (sum == target) ? 1 : 0;
이 부분에 문제가 있어보이네요
if (pos == N - 1 && sum == target) // && sum == target 때문에 끝에 도달했는데 누적된 sum이 target과 일치하지 않는 경우 0을 리턴해줄 수 없겠군요
추가적으로 출력될 수 있는 경우의 수가 int 범위를 넘기 때문에 long long 자료형으로 바꾸셔야합니다
댓글을 작성하려면 로그인해야 합니다.
isvara 4년 전
#include<iostream>
using namespace std;
int N;
int nums[100];
int DP[100][21];
int target;
int Calc(int pos,int sum)
{ //base-case판단
if (pos == N - 1 && sum == target)
return (sum == target) ? 1 : 0;
if (DP[pos][sum] != -1)
return DP[pos][sum];
int ret = 0;
if (sum + nums[pos] <= 20) ret += Calc(pos + 1, sum + nums[pos]);
if (sum - nums[pos] >= 0 ) ret += Calc(pos + 1, sum - nums[pos]);
DP[pos][sum] = ret;
return DP[pos][sum];
}
int main()
{
int cases;
//입력
cin >> N;
for (int i = 0; i < N; i++)
cin >> nums[i];
//초기화
for (int i = 0; i < N; i++)
for (int j = 0; j < 21; j++)
DP[i][j] = -1;
target = nums[N - 1];
cases=Calc(1, nums[0]);
cout << cases << endl;
return 0;
}