백준 1495 - 기타리스트(C++)

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

1495번: 기타리스트

볼륨이 주어졌을 때, 마지막 곡을 연주할 수 있는지 확인하는 문제입니다.

 

시작 볼륨이 주어지고, 변경할 수 있는 볼륨이 주어집니다.

 

시작 볼륨에서 변경할 수 있는 볼륨을 더하고 뺀 값을 전부 확인하면 경우가 너무 많아집니다.

 

따라서 2차원 배열을 이용해 N번 째 볼륨을 바꿀 때, M번 볼륨을 만들 수 있는지를 확인하는 2차원 배열을 만들었습니다.

 

dp[N][M]의 값을 확인하기 위해서, dp[N-1][M]의 값이 있어야지 해당 값에서 더하고 뺄 수 있습니다.

 

해당 값이 존재할 때, dp[N-1][M ± 변경할 수 있는 볼륨]이  0 <=  <= M이 될 때, 값을 저장해줍니다.

 

 

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

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N, S, M;
int V[51];
int dp[51][1001];

void solve(){
    dp[0][S] = 1;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j <= M; j++){
            if(dp[i-1][j] == 1){
                if(j + V[i] <= M) dp[i][j + V[i]] = 1;
                if(j - V[i] >= 0) dp[i][j - V[i]] = 1;
            }
        }
    }
    int maxi = -1;
    for(int i = 0; i <= M; i++){
        if(dp[N][i] == 1) maxi = max(maxi, i);
    }
    cout << maxi;
}

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

 

 

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