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

백준의 기타리스트(1495) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

곡이 넘어갈 때 마다, 음량을 조절할 수 있는데 가장 마지막 곡의 최대 볼륨을 구해야 하는 문제이다.

먼저, 간단하게 수식을 이용해서 문제에 접근해보자.

F[A][B] = true / false 라는 수식을 사용할 것인데, F[A][B] = true의 의미는 "A번째 곡에서, 음량 B로 연주를 할 수 있습니다." 를 의미하고, false인 경우에는 "A번째 곡에서, 음량 B로 연주할 수 없습니다." 를 의미한다.

즉 ! 만약 수식을 정확하게 모두 채웠다면, 우리가 구하고자 하는 정답은 F[N][0 ~ M] 중, 가장 마지막에 true가 있는 값, 즉, 두번째 인덱스 값이 "음량"을 나타내는 인덱스 이므로, 이 인덱스 값이 가장 큰 값이 정답이 된다.

우리에게 주어지는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이를 Volume[] 이라고 표현해보자.

그리고 시작볼륨 S가 주어진다.

그럼, 우리가 첫 번째 곡에서 가질 수 있는 음량을 몇이 될까 ??

바로, S + Volume[1] 혹은 S - Volume[1] 이 된다. 왜냐하면, 주어지는 Volume값 만큼 음량을 더 키울수도 있고, 더 낮출수도 있기 때문이다.

그럼 F[1][S + Volume[1]] = F[1][S - Volume[1]] = true 라고 바로 설정을 해주면 될까 ??

안된다 ! 그 전에 확인해 주어야 할 것이 있다.

S + Volume[1]의 값이 M을 넘는지, S - Volume[1]의 값이 0보다 작아지지는 않는지 확인해 주어야 한다.

만약,넘지 않는다면 F[1][S + Volume[1]] = F[1][S - Volume[1]] = true 라고 설정해 주면 된다.

그럼 ! 두 번째 곡 부터는 어떻게 될까 ?? 두 번째 곡은 "첫 번째 곡에서 사용 가능한 음량에 + , - Volume[2]한 음량을 사용" 하게 된다. 물론 ! 위에서 말했듯이, 그 음량의 범위가 0 ~ M 사이에 있는지 확인을 해야 한다.

즉 ! 적어보면 S + Volume[1] +- Volume[2] , S - Volume[1] +- Volume[2] 가 된다는 것이다.

그럼 ? S + Volume[1], S - Volume[1]의 값을 항상 저장하고 값을 기억하고 있어야 할까 ??

만약 저장하고 기억하고 있어야 한다면, 이게 두 번째 곡이라서 그렇지, 세번째, 네번째 곡으로 가면 갈수록, 저장해야 하는

음량이 점점 더 많아지게 될 것이다.

따라서, 따로 저장을 해놓지는 않을 것이다. 대신 ! "이전 곡에서 사용했던 음량"을 매 곡마다 찾아줄 것이다.

그래서, 이전 곡에서 사용했던 음량을 찾기만 한다면, 그 음량에 + , - Volume[현재곡] 을 하게 된다면, 그리고 저 값이 0 ~ M 이라면 해당 수식의 값을 true로 설정해주는 것을 반복해주면 된다.

코드로 한번 확인해보자.

    if (S + Volume[1] <= M) DP[1][S + Volume[1]] = true;
    if (S - Volume[1] >= 0) DP[1][S - Volume[1]] = true;
    
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (DP[i - 1][j] == true)
            {
                if (j + Volume[i] <= M) DP[i][j + Volume[i]] = true;
                if (j - Volume[i] >= 0) DP[i][j - Volume[i]] = true;
            }
        }
    }

line1 , 2)가 가장 첫 번째곡에 대한 음량을 설정해 주는 부분이다.

line4)의 for문을 보게 되면, 2부터 N까지 반복, 즉 ! 2번곡부터 N번곡까지 반복하는 것을 확인할 수 있다.

line6)의 for문을 보게 되면, 0부터 M까지 반복하는데, 이 과정이 바로 위에서 말했던 "이전 곡에서 사용했던 음량을 찾는 과정" 이다. 실제로 그 안에 조건문(line8)을 보게되면, "이전 곡에서 사용했던 음량이라면" 이라는 조건문이 걸려있다.

따라서 위와 같은 코드를 통해서 우리는 1 ~ N번째 곡에서 사용하는 음량들을 모두 체크해줄 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N, S, M;
int Volume[MAX];
bool DP[MAX][1010];
 
void Input()
{
    cin >> N >> S >> M;
    for (int i = 1; i <= N; i++) cin >> Volume[i];
}
 
void Solution()
{
    if (S + Volume[1] <= M) DP[1][S + Volume[1]] = true;
    if (S - Volume[1] >= 0) DP[1][S - Volume[1]] = true;
    
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (DP[i - 1][j] == true)
            {
                if (j + Volume[i] <= M) DP[i][j + Volume[i]] = true;
                if (j - Volume[i] >= 0) DP[i][j - Volume[i]] = true;
            }
        }
    }
    for (int i = M; i >= 0; i--)
    {
        if (DP[N][i] == true)
        {
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}