[백준 1495] - 기타리스트(C++)[실버1]

📕문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V [i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V [i]나 P-V [i]로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

📗입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

📗출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

👀문제 해석

• 문제를 읽어보면 DP를 사용하라는 힌트가 있다.
• 즉 우리는 i번째 곡을 연주하기 전에 i-1번째 볼륨을 이용해서 i번째 곡의 볼륨을 조절해야 한다.

🔎문제 풀이

• 초기에는 1차원 배열로만 만들어서 n*n 반복문을 돌려서 풀려고 했었는데, 도저히 감이 안잡혀서
  2차원 배열로 풀었다. [최대한 DP는 1차원 배열로 풀고싶었는데, 쉽지가 않다.]
• 2차원 배열로 풀면 굉장히 쉬운 문제이다.
• n+1*m+1 배열로 배열의 크기를 선언한다.
  • row는 곡의 순서라고 생각하면 편하다.
    DP[1][]는 1번째 곡을 치는데 만들수 있는 볼륨들의 집합이다.
  • col는 곡의 볼륨이라고 생각하면 편하다.
     DP[1][5]는 1번째 곡을 치는데 5라는 볼륨을 조절할 수 있는지에 대한 결과가 들어가게 된다.

• 위의 그림을 설명해보자면
• 0번째 곡에는 시작볼륨만 만들 수 있다.
• 1번째 곡에는 이전곡에서 만들었던 볼륨에 대해서 1번째 볼륨을 빼거나 더해줘야한다.
  • 여기서 문제조건에 따라서 뺄때는 0이상, 더할때는 M이하여야 한다.
• 2번째 곡에는 이전곡(1번째곡)에서 만들었던 볼륨에 대해서 2번째 볼륨을 빼거나 더해줘야 한다.
• 이렇게 쭉쭉 가다가
• 맨 마지막 곡을 칠때 체크된 열들중 가장 나중에 체크된 열에 해당하는 값이 n곡을 칠 때의 최대 볼륨이다.
  • 만약 마지막 곡을 칠때 체크된 곳이 없다면 마지막곡까지 볼륨을 조절할 수 없다는 뜻이므로 -1을 출력한다.

 

💻코드

/*
실버1 기타리스트
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, s, m;
vector<int> volume;
vector<vector<int>> DP;
int main()
{
    int Max = -1;
    cin >> n >> s >> m;
    volume.resize(n + 1, 0);
    DP.resize(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        cin >> volume[i];
    }
    DP[0][s] = 1; //시작볼륨 s는 만들 수 있어야함.
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            if (DP[i - 1][j] == 1) //i-1번째 곡에서 j 크기의 볼륨을 만들 수 있을 때
            {              
                if (j + volume[i] <= m)
                {                 
                    DP[i][j + volume[i]] = 1;
                }
                if (j - volume[i] >= 0)
                {                   
                    DP[i][j - volume[i]] = 1;
                }
            }
        }
    }
    for(int i=0; i<=m;i++){    
        if(DP[n][i]==1){
            Max=max(Max,i);
        }
    }  
    cout<<Max;  
    
}

 

✔느낀 점

• 메모리에 대한 개념을 좀 잡아야 할 것 같다.
  • 이 개념을 잡아야 입력값에 따라 2차원 배열로 짜도 되는지 안되는지를 인지할 것 같다.
• DP는 2차원 배열로 짜면 진짜진짜로 편하다!