[BOJ 5557] 1학년(메모리 초과 발생 이유)

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

5557번: 1학년

 

 

이 문제는 다이나믹 프로그래밍 문제이다.

 

 

 

 

다이나믹 프로그래밍의 본질은, 큰 문제를 작은 문제를 통해서 해결한다라는 것을 잊지말자!

 

 

 

 

i번까지의 연산의 값을, 이전에 구해놓은 연산을 통해서 구할 수 있다.

 

 

 

 

이전에 구해놓은 값들 + i번째 값

이전에 구해놓은 값들 - i번째 값

 

 

 

 

위의 관계를 점화식으로, 작성을 해야 한다. 

 

 

 

 

만약 vector를 선언하고, 거기다가 차례로 i번째까지 값을 저장해놓으면 메모리초과가 발생할 것이다.

 

 

 

 

따라서, vector라는 별도의 자료구조없이 문제를 해결해야 한다.

 

 

 

 

DP[i][j] = i번째까지 연산을 했을 때, j라는 값이 나온 횟수

 

 

 

 

라고 정의하면 문제를 해결할 수 있다.

 

 

 

 

 

해설코드(C++).

 

#include <iostream>

using namespace std;

 

int N;

long long arr[101];

long long dp[101][21];

 

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 - 1; i++){

        for(int j = 0; j <= 20; j++){

            if(dp[i - 1][j] == 0)

                continue;

                

            int val1 = j + arr[i];

            int val2 = j - arr[i];

            

            if(val1 <= 20)

                dp[i][val1] += dp[i - 1][j];

                

            if(val2 >= 0)

                dp[i][val2] += dp[i - 1][j];

        }

    }

    

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

    return 0;

}