[백준 1495번] 기타리스트 (C++)

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

1495번: 기타리스트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

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

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> S >> M; //갯수, 시작 볼륨, 최대치
    for(int i=1; i<=N; i++) cin >> arr[i];

    dp[0][S]=1;

    for(int i=1; i<=N; i++) //갯수
    {
        for(int j=0; j<=M; j++) //최대 볼륨
        {
            if(!dp[i-1][j]) continue;
            if(j+arr[i] <= M) dp[i][j+arr[i]] = 1;
            if(j-arr[i] >= 0) dp[i][j-arr[i]] = 1;
        }
    }

    for(int i=M; i>=0; i--)
    {
        if(!dp[N][i]) continue;
        cout << i;
        return 0;
    }
    cout << -1;
    return 0;
}

 

dp식을 곡의 갯수와 볼륨 수치로 정해 2차원 배열로 선언해준다.

이때 만든 2차원 배열은 현재 갯수 및 볼륨에 대해 가능여부를 판별하기에 값은 1 or 0만 들어가게 된다.

초기값으로 시작 볼륨 S를 참고하여 dp[0][S]를 1로 초기화한다. (해당 볼륨 선택 가능을 의미)

 

이후 2중 반복문을 돌리며 체크를 하게 된다.

먼저 이전 곡의 위치를 확인하여 해당 곡의 볼륨이 있는지 없는지를 체크한다.

있다면 이어서 가능한 볼륨수치를 체크하게 되고 아니라면 스킵하게 된다.

바로 체크하는 것이 아닌 추가로 2가지를 탐색하는데 문제에 주어진 것처럼 현재 볼륨에 바꿀 수 있는 볼륨 수치를 더하거나 뺀 범위를 체크하여 현재 볼륨 수치가 변경 가능한 수치인지 확인을 해주어야 한다.

 

더한 경우는 M보다 같거나 작아야 하고, 뺸 경우는 0보다 크거나 같아야 한다.

만약 무사히 범위조건에 맞는다면, 현재 곡 및 변경한 볼륨수치에 해당하는 dp에 1을 표기하여 준다.

이를 반복하여 탐색하게 된다.

 

이후 최대 볼륨을 찾기 위해 볼륨을 M~0까지 반복문을 돌리며 확인하게 된다.

만약 가능한 값이 있다면 바로 출력하고 중료시켜주는데 이는 볼륨을 M부터 확인하여 바로 가능한 최대수치를 출력하게 되기 때문이다.

반복문을 통해 아무것도 출력을 하지 못했다면 가능한 볼륨수치가 존재하지 않는 것이기에 -1을 출력하게 된다.