백준 5557 - 1학년(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5557

5557번: 1학년

DP를 이용해 푸는 문제였습니다.

주어진 수에서 +, -를 이용해 식을 만들 때, N번째 수의 값을 만들 수 있는지 확인하는 문제입니다.

 

1~N-1까지의 수를 이용해야하는데, 한 수를 거칠 때마다 경우가 2배씩 늘어납니다.

그렇다면 최악의 경우 2^99개까지 경우가 만들어지는데, 이러면 시간초과가 생깁니다.

 

문제의 조건을 본다면, 계산할 때마다 나오는 값의 범위가 항상 0~20사이라고 주어졌습니다.

따라서 어떤 값을 계산 했을 때, 해당 범위를 넘어서는 값이 있다면 일단 무시하면 됩니다.

 

값을 차례대로 계산하는 방법을 사용해야되기에, [0~20][1~N까지 단계]로 배열을 저장해줬습니다.

 

예를 들어, 5번째 수를 더하거나 빼야할 때,

4번까지의 계산 값을 이용하면 됩니다. 

->[0~20][4] 의 값을 확인해 값이 존재하는 곳을 찾은 뒤, 조건에 따라 값을 넣어주면 됩니다.

 

해당 방법을 사용한다면 시간초과 없이 문제를 풀 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

long long dp[21][101];
int N;
int arr[101];

void solve(){
    dp[arr[1]][1] = 1;
    for(int i = 2; i < N; i++){
        for(int j = 0; j <= 20; j++){
            if(dp[j][i-1] == 0) continue;
            if(j - arr[i] >= 0) dp[j-arr[i]][i] += dp[j][i-1];
            if(j + arr[i] <= 20) dp[j+arr[i]][i] += dp[j][i-1];
        }
    }
    cout << dp[arr[N]][N-1];
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> arr[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.