[5557] 1학년

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

5557번: 1학년

<문제>

6

5 2 1 4 1 7 같은 입력이 들어오면,

5 - 2 - 1+ 4 + 1 = 7 처럼 n-1개의 수를 더하거나 빼 n번째 숫자를 만들 수 있는 경우의 수를 세야한다.

이와 더불어, 왼쪽부터 차례대로 계산할때 값이 항상 0이상 20이하인 경우의 수만 세야한다.

다이나믹으로 해결할 수 있는 문제이고

dp[i][j]에서 i를 숫자의 개수, [j]를 숫자의 값으로 놓으면

우리가 구해야하는 답은 n-1개의 숫자를 사용해 a[n]을 만드는, dp[n-1][a[n]]이 된다.

 

 

<소스코드>

#include<stdio.h>
int a[101], n;
long long dp[101][21];
int main(void) {
    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    dp[1][a[1]] = 1;
    for (i = 2; i <= n; i++) {
        for (j = 0; j <= 20; j++) {
            if (j - a[i] >= 0)
                dp[i][j] += dp[i - 1][j - a[i]];
            if (j + a[i] <= 20)
                dp[i][j] += dp[i - 1][j + a[i]];
        }
    }
    printf("%lld", dp[n-1][a[n]]);
    return 0;
}