[ SWEA 5685 ] 초등학생 (C++)

SWExpertAcademy의 초등학생(5685 / D5) 문제이다.

[ 문제풀이 ]

주어진 숫자들 사이에 + 혹은 - 기호를 넣어서 최종적으로 가장 마지막 숫자가 나오게 만들어 주어야 하는 문제이다.

지금부터는 문제를 수식으로 표현해 볼 것인데, F[A][B] = C 라는 수식을 사용해 볼 것이다.

이 수식의 의미는, "주어진 배열에서 A번 Index까지 왔을 때, B라는 숫자를 만들 수 있는 방법은 총 C가지가 있습니다." 를 의미한다.

그럼 지금부터 다음과 같은 상황을 생각해보자.

우리는 현재 "x번째 위치한 A라는 값"을 통해서 'K' 라는 숫자를 만들고 싶은 상황이다.

그럼, 우리는 2가지 방법을 고려해 볼 수 있다.

기존에 나왔던 숫자들(1번 ~ x - 1번 까지 계산했을 때 나올 수 있는 값들) 에서 A를 빼줌으로써 K를 만드는 경우와,

A를 더해줌으로써 K를 만드는 경우이다.

그렇다면 이를 수식으로 나타내보자.

"x번째 위치한 숫자를 통해서 K를 만드는 경우" 이니, F[x][K] 가 될 것이다.

그럼 F[x][K] = ?. 에서 ? 에 들어갈 값은 어떤 값이 될까 ??

바로, x - 1번째 값 까지 계산해서 K - A 를 만드는 경우와, K + A를 만드는 경우가 될 것이다.

왜냐하면 x - 1번째 값 까지 계산해서  K - A를 만들었다면, K - A에 x번째 있는 A를 더해서 K를 만들 수 있을 것이고,

x - 1번째 값 까지 계산해서 K + A 를 만들었다면, K + A에 x번째 있는 A를 빼서 K를 만들 수 있기 때문이다.

즉, F[x][K] = F[x - 1][K - A] + F[x - 1][K + A] 가 될 것이다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 110
#define MODULER 1234567891
using namespace std;
 
int N, Last, Answer;
int Arr[MAX];
long long DP[MAX][25];
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i < N; i++) cin >> Arr[i];
    cin >> Last;
}
 
void Solution()
{
    DP[1][Arr[1]] = 1;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= 20; j++)
        {
            if (j - Arr[i] >= 0) DP[i][j] = (DP[i][j] + DP[i - 1][j - Arr[i]]) % MODULER;
            if (j + Arr[i] <= 20) DP[i][j] = (DP[i][j] + DP[i - 1][j + Arr[i]]) % MODULER;
        }
    }
    Answer = DP[N - 1][Last] % MODULER;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}