백준 5557번 1학년

문제 링크 : https://www.acmicpc.net/problem/5557

5557번: 1학년

 

문제 설명

N개의 숫자가 주어졌을 때, N-1 개의 수 가운데에 + 또는 - 를 추가하여 n번 째 수를 만들 수 있는

등식의 개수를 출력하는 문제이다.

 

풀이

다이내믹 프로그래밍 문제입니다!

이 문제의 좋은 점은 중간에 나오는 수가 모두 0 이상 20 이하라는 조건이 있기 때문에

dp로 풀 수 있다는 것이다.

d[i][j] : 숫자 i번까지의 등식 결괏값이 j

로 설정해두고, j가 0 미만이거나 20 초과이면 계산하지 않는다.

 

소스 코드

#include <iostream>
#include <cstring>
using namespace std;
 
long long d[101][21]; // d[i][j] : i번까지 더한 결과 j
int a[101];
int sum = 0;
int main()
{
    int n; scanf("%d", &n);
    memset(d, 0, sizeof(d));
    for (int i = 0; i < n-1; i++) { //1 ~ n-1
        scanf("%d", &a[i]);
    }
    scanf("%d", &sum);
    d[0][a[0]] = 1; //initial
    for (int i = 1; i < n - 1; i++) { // 1 ~ n-1
        for (int j = 0; j <= 20; j++) { // 0 ~ 20
            if (0<= j + a[i] && j + a[i] <= 20) {
                d[i][j] += d[i - 1][j + a[i]];
            }
            if (j - a[i] >= 0 && j - a[i] <= 20) {
                d[i][j] += d[i - 1][j - a[i]];
            }
        }
    }
    printf("%lld\n", d[n - 2][sum]);
    return 0;
}

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~