백준, BOJ, 5557번, 1학년 : C++ [CPP]

솔직히 바로 생각을 못했다.

값을 다 계산해야하나? 싶었다.

 

하지만 힌트를 보고야 말았으니..

즉, N개의 수에서 N-1번만 조사하면 되는 것이고

N-1까지의 경우의 수를 구하려면..?

N-2에서 N-1번째 원소를 더하거

나 빼는 경우를 세어주면 되었다.

 

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

 

---

 

#맞은 풀이

#include <iostream>

using namespace std;

int N;

int arr[101];
long long dp[101][21]; //N번째에 K값이 나오는 경우의 수


int main(){
    long long ans; //답의 범위가 2^63-1임
    
    cin >> N;
    for(int i =1; i<=N; i++){
        cin >> arr[i];
    }
    
    int target = arr[N];
    
    
    //초기값
    dp[1][arr[1]] = 1; //가장 처음의 수는 무조건 들어감 (1개)
    
    for(int i = 2; i<=N-1; i++){
        for(int j = 0; j<=20; j++){
            if(dp[i-1][j] == 0)continue; //해당 값을 가지는 결과가 없으면 넘어감
            
            //현재 위치의 값을 더해서 범위 안에 있다면 이전에 해당 값을 가지는 경우가 다 더해짐.
            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];
            }
        }
    }
    
    ans = dp[N-1][target]; //target의 값과 같은 경우의 수
    
    cout << ans;
    
    
    
    return 0;
}

 

 

다시 말하자면..

결국 구하는 것은 N개의 수에서 N번째 원소는 비교 대상

N-1까지 계산했을 값의 경우의 수를 알고 싶다는 것이다.

 

그렇다면 임의의 n번째에서 임의의 결과값 m을 가지는 경우의 수를 어떻게 구할까?

n-1번째의 결괏값 중에서 n번째 위치의 원소를 더했을 때 m을 가지는 경우

+

n-1번째의 결괏값 중에서 n번째 위치의 원소를 뺐을 때 m을 가지는 경우

를 구하면 되겠구나?

 

하지만 우리가 셀 것은 20이 넘지 않게끔 세어야한다.

즉, 계산 도중에 20이 넘거나 음수가 되면 세지 않아도 된다.

 

즉, 계산을 하면서 0~20까지의 결괏값만 저장하면 된다는 뜻이다.