[C++] 백준 5557번 1학년

다이나믹 프로그래밍 문제입니다.

덧셈과 뺄셈을 이용해서 마지막  숫자를 만들어야 하며
왼쪽부터 계산을 하며 계산 과정에서 음수가 나오거나 20을 넘으면 안됩니다.
이 때 경우의 수를 구하는 문제입니다.

왼쪽부터 차례대로 +와 -에 대해서 모두 계산을 합니다.
음수가 아니고 21보다 작으면 DP[i][j]에 넣어줍니다.
이 때 i는 현재 위치이고 j는 0~20의 값을 의미합니다.

위의 예제에서
처음 8은
DP[1][8] = 1로 나타낼 수 있으며

두번 째 3은
DP[2][8+3] += DP[1][8];
DP[2][8-3] += DP[1][8];
으로 나타낼 수 있습니다.

#include <iostream>
#include <cstring>
using namespace std;

int n;
int arr[110];
long long int DP[110][30];

void solve(int x)
{
  if (x == n)
  {
    return;
  }
  for (int i = 0; i <= 20; ++i)
  {
    if (DP[x - 1][i] != 0)
    {
      if (i + arr[x] <= 20)
      {
        DP[x][i + arr[x]] += DP[x - 1][i];
      }
      if (i - arr[x] >= 0)
      {
        DP[x][i - arr[x]] += DP[x - 1][i];
      }
    }
  }
}

int main(int argc, char *argv[])
{
  int sum = 0;
  memset(arr, 0, sizeof(arr));

  cin >> n;

  for (int i = 1; i <= n; ++i)
  {
    cin >> arr[i];
  }

  DP[1][arr[1]] = 1;

  for (int i = 2; i <= n; ++i)
  {
    solve(i);
  }

  cout << DP[n - 1][arr[n]] << endl;

  return 0;
}