[백준] 1학년 5557번 (c++) dp

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

풀이 방법

dp를 설정하는 것에 시간이 많이 쓴 거 같다

결정한 방법은 dp[y][x] == y번째 자리일 때까지의 합이 x인 경우로 설정했다.

또한 만약 dp[y][x]의 값이 0이라면 해당 경우는 가능하지 않은 경우 이므로 선택하지 않는다.

결국 dp[y][x]의 값이 양수인 것 중에서만 dp[y-1][x-number[i]]를 더해주거나 빼주면 된다. (0 이상 20 이하 인경우만)

 

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

int N;
vector<int> number;
long long dp[101][21];

int main() {
    memset(dp, 0, sizeof(dp)); //dp 배열 초기화

    cin >> N;
    for (int i = 0;i < N;i++) {
        int a;
        cin >> a;
        number.push_back(a);
    }
    //dp[i][j] == i번째에 j일때 경우의 수
    dp[0][number[0]] = 1;
    for (int i = 1; i < N-1;i++) {
        for (int j =0;j < 21;j++) {
            if (dp[i-1][j] != 0) {
                int next = number[i];
                if (j + next <= 20) {
                    dp[i][j+next] += dp[i-1][j];
                }
                if (j - next >= 0) {
                    dp[i][j-next] += dp[i-1][j];
                }
            }
        }
    }
    cout << dp[N-2][number[N-1]];
    return 0;
}