백준 5557 / 1학년

다이나믹 프로그래밍 문제

기타리스트 문제와 해결법은 (https://naivep.tistory.com/73) 동일하다.

D[n][i] 배열을 n번째 숫자에 도달했을 때 i(0<=i<=20)를 만들 수 있는 경우의 개수를 뜻한다.

여기서 경우의 개수가 굉장히 많기 때문에 (문제에도 나왔듯 2^63-1 이하)

 

D 배열을 long 혹은 long long으로 선언해야한다.

double로 선언하면 정확하지 않다 (정수형 배열이 아니라 그런가.. 정확한 건 모르겠다)

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int num[101];
long long d[101][21];
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
 
    d[0][num[0]] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 20; j++) {
            if (d[i][j] != 0) {
                long long a = d[i][j];
 
                if (j + num[i + 1] <= 20) {
                    d[i + 1][j + num[i + 1]]+=a;
                }
                if (j - num[i + 1] >= 0) {
                    d[i + 1][j - num[i + 1]]+=a;
                }
 
            }
        }
    }
 
    cout << d[n - 2][num[n - 1]];
 
}