백준 5557번 : 1학년

  흑흑 상근아... 왜 그런 취미를 가지고 있니ㅠㅠ 좀 더 유익한 취미를 가지렴.. 차라리 스도쿠를 하는게 어떻겠니....?

 

  처음 문제를 봤을 때 숫자를 임의로 더하고 빼면 한 번 계산할 때마다 가짓수가 2배가 되는데 이게 가능한건가? 싶었는데 잘 보니 우리 상근이는 1학년이라서 숫자를 0부터 20까지 밖에 모른다고 한다. 오.. 상근아... 고마워!! 따라서 어떻게 계산을 하더라도 계산의 결괏값 즉, 치역은 21개 밖에 존재하지 않는다는 뜻이다. 마침 수열의 최대 갯수도 99개이기 때문에 100 * 21 짜리 배열을 만들어서 저장해두면서 사용하도록 하자.

 

dp[i][j]

수열의 i번째 항까지 계산을 했을 때 j라는 값이 될 경우의 수

 

  문제의 구조는 기본적인 냅색문제와 같다. dp[i][j]는 dp[i-1]에 있는 항들 중 자기 자신을 더했을 때 j라는 값이 되는 녀석들의 합이다. 예를 들어 수열의 4번째 항이 4이였고 dp[4][6] = 3이였다면 dp[5][2]는 dp[4][6]에서 4를 뺐을 때 도달할 수 있고 dp[5][10]은 dp[4][6]에서 4를 더했을 때 도달할 수 있으니 dp[5][2]와 dp[5][10]에 각각 dp[4][6]의 값만큼(=3) 더해줘야한다. 이 과정을 첫번째 항부터 마지막 항까지 for문을 통해 반복해주면 된다. 주의할 점은 문제에서 정답의 갯수가 int의 범위로는 커버할 수 없다고 제시되어 있기 때문에 dp행렬을 long long으로 선언해주기만 하면 된다.

#include <iostream>

using namespace std;

int n;
int seq[102];
long long dp[102][21];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> seq[i];
    }
    
    dp[0][seq[0]] = 1;
    
    for(int i = 1; i < n - 1; i++)
    {
        for(int j = 0; j <= 20; j++)
        {
            if(dp[i-1][j] == 0) continue;
            
            if(j + seq[i] <= 20) dp[i][j+seq[i]] += dp[i-1][j];
            if(j - seq[i] >= 0) dp[i][j-seq[i]] += dp[i-1][j];
        }
    }
    
    cout << dp[n-2][seq[n-1]];
}