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

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

 

 

[ 문제 요약 ]

N개의 숫자가 주어질 때 +, -를 넣어 등식을 만든다. 이때 중간에 나오는 수가 모두 0 이상 20 이하이어야 할 때 만들 수 있는 올바른 등식의 개수를 출력한다.

 

 

[ 문제 풀이 ]

1. 우선 가장 먼저 첫번째 수는 계산하지 않기 때문에 바로 넣는다.

2. 쓸 수 있는 기호가 +, - 만 있기 때문에 특정한 수를 더하거나 뺐을 때 가능하다면 그 수의 값에 맞게 배열에 더한다.

3. 마지막 값이 답이 되어야 하기 때문에 이전까지의 값을 모두 계산했을 때 답이 마지막 값인 경우를 확인한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[101];
long long dp[101][22];

int main() {
    cin >> N;
    for (int i=1; i<=N; i++) cin >> arr[i];

    dp[1][arr[1]] = 1;

    for (int i=2; i<N; i++){
        for (int j=0; j<=20; j++){
            if (dp[i-1][j]){
                if (j + arr[i] <= 20) dp[i][j + arr[i]] += dp[i - 1][j];
                if (j - arr[i] >= 0) dp[i][j - arr[i]] += dp[i - 1][j];
            }
        }
    }

    cout << dp[N - 1][arr[N]];

    return 0;
}

 

 

 

[ 주의할 점 ]

Knapsack problem(배낭 문제)와 비슷한 방식으로 문제를 풀 수 있었다.