[백준] 5557번 : 1학년 (C++)

5557번 : 1학년

---

문제)

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

 

 

 

출력 :

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

 

 

 

 

 

 

 

 

풀이)

 

// 5557. 1학년
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> vec;
long long dp[102][21];
 
long long recur(int cur, int total)
{
 
    if (total > 20 || total < 0) return 0;
    
    if (dp[cur][total] != -1) return dp[cur][total];
    
    if (cur == n - 1)
    {
        if (total == vec[cur]) return 1;
        return 0;
    }
 
    long long ret = 0;
 
    ret += recur(cur + 1, total + vec[cur]);
    ret += recur(cur + 1, total - vec[cur]);
 
    dp[cur][total] = ret;
 
    return dp[cur][total];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    vec.resize(n);
    fill(&dp[0][0], &dp[101][21], -1);
    for (auto& i : vec) cin >> i;
 
    // 한가지 엣지케이스때문에 1번 인덱스를 넣어줘야함.
    // 맨 처음의 수가 0이 나왔을 경우
    // +0, -0으로 분기가 갈라지기 때문에 
    // 틀린 답이 나오게 된다.
    // 따라서 1번 인덱스, vec[0]을 넣어 시작해야 한다.
    cout << recur(1, vec[0]);
 
 
    return 0;
}

---

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

5557번: 1학년