[백준]: 5557번: 1학년 / DP(동적프로그래밍)

https://www.acmicpc.net/problem/5557

해당문제는 N이 주어졌을 때, n-1까지의 +또는 - 의 값이 0<=Result<=20 사이로 들어와야 한다는 것이다.

간단하게 생각하면 재귀를 통해서 해결할 수 있다. 

그리고 생각없이 int형으로 return받다가 틀렸다고 떴는데, 2^100(2^N)이 꽤 크기에 int형으로 담지못한다. 따라서 long long타입으로 해야한다.

간단한 로직으로 설명하자면,

1. 기저조건 -> N== Index 가 맞는지? 맞다면 arr[N]==result가 같은지 (yes -> dp[index][result] ->1 / no -> dp[index][result] ->1

2. 미리계산한 값이라면 중복을 제거한다.

3. 재귀수행( result +arr[index] or result- arr[index] )

#include<iostream>

using namespace std;

#include<algorithm>

int n;

#include<cstring>

long long arr[105];

long long dp[200][200]; //iidx, sum 으로 

long long DP(int x,int result)

{

if (result < 0 || result>20)return 0;

if (x == n)

{

if (result == arr[x])

dp[x][result] = 1;

else

dp[x][result] = 0;

return dp[x][result];

}

if (dp[x][result] != -1)return dp[x][result];

long long ret = 0;

ret += DP(x + 1, result+ arr[x] );

ret += DP(x + 1, result-arr[x] );

dp[x][result] = ret;

return  dp[x][result];

} 

int main()

{

cin >> n;

memset(dp, -1, sizeof(dp));

for (int i = 1 ; i <= n  ; i++)

cin >> arr[i];

cout << DP(2, arr[1]) << "\n";

return 0;

}