[백준 c++] 5557 1학년

문제

https://www.acmicpc.net/problem/5557
N개의 숫자가 주어진다.
마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들 경우의 수를 구하자.
단, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하여야 한다.

풀이

완전탐색을 해야하니 dp를 이용해서 풀었다.
dp에 어떤 값을 저장해둬야할까?
트리를 그려 생각해보자.특정 index에서 중간 계산 값에 대한 경우의 수는 한번만 계산해두면 되겠다.
=> dp[idx][sum]

범위 체크(0~20),
마지막 인덱스까지 왔으면 맨 마지막 수랑 같으면 return 1 아니면 return 0,
빼거나 더해야하므로 각각 재귀 함수 호출

🚨 출력 범위가 2^63-1 이하라서 자료형에 주의해야한다.

코드

#include <iostream>
using namespace std;
typedef long long ll;
int n, a[101];
ll dp[101][21]; // 인덱스, 값
ll go(int idx, int sum)
{
    if (sum < 0 || sum > 20)
        return 0;
    if (idx == n - 2)
    {
        if (sum == a[n - 1])
            return 1;
        return 0;
    }
    if (dp[idx][sum])
        return dp[idx][sum];

    dp[idx][sum] += go(idx + 1, sum - a[idx + 1]);
    dp[idx][sum] += go(idx + 1, sum + a[idx + 1]);

    return dp[idx][sum];
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    cout << go(0, a[0]) << "\n";
}