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;
}

tmdfur11   3년 전

if (pos == N - 1 && sum == target)
return (sum == target) ? 1 : 0;

이 부분에 문제가 있어보이네요

if (pos == N - 1 && sum == target) // && sum == target 때문에 끝에 도달했는데 누적된 sum이 target과 일치하지 않는 경우 0을 리턴해줄 수 없겠군요

tmdfur11   3년 전

추가적으로 출력될 수 있는 경우의 수가 int 범위를 넘기 때문에 long long 자료형으로 바꾸셔야합니다

댓글을 작성하려면 로그인해야 합니다.