1495 기타리스트 (dp)

1495번: 기타리스트 (acmicpc.net)

1495번: 기타리스트

노래를 차례대로 불러가며 마지막 노래에서의 최대 볼륨을 구하는 문제였습니다.

완전탐색의 경우 볼륨을 더하고 빼는데 2^100 만큼 걸릴 수 있으며 시간내에 해결하기 어려워보입니다.

 

풀이과정

cache[index][volumn] = index번째 노래이며 볼륨이 vol 일때 마지막 노래의 최대 볼륨값 저장

이렇게 놓을 수 있으며 볼륨을 더하고 뺄 수 있는 기준은 0 <= volumn <= M 이므로

해당 범위 내에 있으면 재귀호출을 통해 최대값을 찾아나가는 방식으로 해결할 수 있습니다.

 

다만 문제에서 불가능한 경우를 따로 -1로 출력하라고 했는데,

"불가능한 경우"를 -1로 그대로 놓을 경우 "이미 계산한 경우" 와 구분이 되질 않기 때문에

메모이제이션이 제대로 작동하지 않아서 시간초과가 발생하는 문제가 발생하였습니다.

 

따라서 불가능한 경우를 -2로 지정해주었습니다.

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
// 곡 개수 , 시작 볼륨 , 최대 볼륨
int N,S,M;
int songs[101];
// index번째 노래이며 볼륨이 vol일때 마지막 노래에서의 최대 볼륨
int cache[101][1001];

int solution(int idx, int vol) {
    if(idx == N)
        return vol;
    int &ret = cache[idx][vol];
    if(ret != -1) return ret;

    // 초기값으로 불가능한 경우를 -2로 해주었다.
    // -1로 해줄 경우 불가능한지 아니면 이미 계산한건지 알 수 없기때문에
    // 위의 ret != -1 부분에서 메모이제이션이 제대로 이루어지지 않아서 시간초과가 발생한다
    ret = -2;
    if(vol+songs[idx] <= M)
        ret = max(ret,solution(idx+1,vol+songs[idx]));
    if(vol-songs[idx] >= 0)
        ret = max(ret,solution(idx+1,vol-songs[idx]));
    return ret;
}

int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d %d %d",&N,&S,&M);
    for(int i=0; i<N; i++)
        scanf("%d",&songs[i]);
    int result = solution(0,S);
    if(result == -2) printf("-1");
    else printf("%d\n",result);
}