[BOJ] 1학년 5557번 C++

 

 

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다

 

접근 방식

 

이걸 어떻게 점화식을 만들어야 할지 처음에 감이 안왔다

각자리 숫자를 더하거나 뺄 때 0~20 사이의 값이 나오면 해당 점화식을 처리해주고 마지막 값을 제외하고 해당 등식의 값이 가장 마지막 값이 되면 출력임은 인지를 했지만

이걸 어떻게 DP로 풀어야할지 막막했다

 

그런데 풀이는 생각보다 쉬웠다는..!

DP 배열은 2차원 배열로 잡고, DP[i][j]는  i번째까지 고려했을 때 j값을 만들수있으면 이전 값에서 더해주면 된다

만약 j 에다가 현재 num[i]를 더했을 때 20보다 작으면 dp[i][j+num[i]] += dp[i-1][j]해주면 되고

만약 뺄 때 0보다 크면 dp[i][j-num[i]] += dp[i-1][j] 해주면 된다!

 

점화식은 진짜 간단한데 생각하기까지가 어려웠던 문제... ㅜ

 

코드

 

#include<bits/stdc++.h>
using namespace std;

long long dp[103][21]; // i번째 까지 고려해서 만들수있는 수 j

int main() {
    int N; cin>>N;
    int num[103];
    for(int i=0; i<N; i++) cin>>num[i];

    dp[0][num[0]] = 1;
    
    for(int i=1; i<N-1; i++) {
        for(int j=0; j<=20; j++) {
            if(dp[i-1][j]) {
                if(j + num[i] <= 20) dp[i][j+num[i]] += dp[i-1][j];
                if(j - num[i] >= 0) dp[i][j-num[i]] += dp[i-1][j];
            }
        }

    }
    cout<<dp[N-2][num[N-1]];

}