백준 5557번, 1학년(C,C++)

5557번: 1학년 (acmicpc.net)

5557번: 1학년

 

해당 문제는 다이나믹 프로그래밍으로 해결하였습니다.

 

도무지 생각해도 아이디어가 안 떠올랐다.

고민하다가 hint를 보게 되었는데

• 8+3-2-4+8-7-2-4-0+8=8
• 8+3-2-4+8-7-2-4+0+8=8
• 8+3+2+4-8-7+2-4-0+8=8
• 8+3+2+4-8-7+2-4+0+8=8
• 8+3+2-4+8-7+2+4-0-8=8
• 8+3+2-4+8-7+2+4+0-8=8
• 8-3+2+4-8+7+2+4-0-8=8
• 8-3+2+4-8+7+2+4+0-8=8
• 8-3+2-4+8+7+2-4-0-8=8
• 8-3+2-4+8+7+2-4+0-8=8

N번째 숫자는 ,1번에서 N-1번째까지 연산했을 때의 값과 같다.

간단하게 말해서

N = 4이고  {1, 2, 3, 6}이 있다.

 

1 + 2 + 3 = 6

6 = 6이라는 뜻이다.

 

한칸을 줄여 N = 3인 경우 {1, 2, 3}

 

1 + 2  = 3

3 = 3인데,

여기서 알아채야 하는 부분은

 

!! N = 4가 올바른 등식이려면 N = 3도 올바른 등식이여야 한다는 뜻이다.

 

또한

1번 숫자부터 N-2번째 숫자까지 연산한 값 +  N-1번째 숫자 값 = N번째 숫자라는 것을 알 수 있다.

 

위 힌트에서 알 수 있듯이 빼기인 경우도 마찬가지다. 

 

1번 숫자부터 N-2번째 숫자까지 연산한 값 -  N-1번째 숫자 값 = N번째 숫자라는 것을 알 수 있다.

 

 

따라서 2가지를 if문을 통해 나눠서 수행할 것이다.

 

#include<iostream>

using namespace std;

int main(){
    int N;
    long long dp[101][21]={0,};
    int arr[101]={0,};
    cin>>N;
    
    
    for(int i = 1; i <= N; i++){
        cin>>arr[i];
    }
    int K = arr[N];

    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;
            }

            if(arr[i] + j <= 20){
                dp[i][j+arr[i]] += dp[i-1][j];
            }

            if(j - arr[i] >= 0){
                dp[i][j-arr[i]] += dp[i-1][j];
            }
        }
    }
    long long solution = dp[N-1][K];
    cout<<solution;

    return 0;
}