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

문제

www.acmicpc.net/problem/1495

1495번: 기타리스트

 

풀이

 

Top_bottom 풀이

 

해당 순서(order)의 설정된 볼륨(volume)에서 다음 볼륨의 설정 값을 더하거나 빼주는 경우로 분기한다.

이때 두 가지 분기의 결과 중 더 큰 값을 저장하여 같은 값의 연산을 방지해준다.

 

모든 순서에서의 볼륨값을 탐색하여도 시간 복잡도는 O(NM)이므로 충분히 시간 안에 계산이 가능하다.

 

만약 현재의 볼륨에서 다음 설정 값으로 모두 변경이 불가능한 경우, 예를 들어 현재의 값이 5이고 최대 볼륨 값이 7인 경우를 생각해보자.

 

다음 설정 값은 6이라면 더하고 빼주는 경우 모두 불가능한 조절이다. 이런 경우 해당 cache값을 -2로 설정하여 방문을 하였고 불가능한 경우임을 저장한다.

 

해당 코드는 페이지의 마지막 부분 참조.

 

 

 

Bottom-Up 풀이

 

bottom-up에서는 cache값을 방문이 가능한지 여부만 확인하면 되기 때문에 bool형으로 선언한다.

 

현재 순서에서 다음 볼륨으로 설정이 가능한 경우

cache[order+1][next_volume]가 방문이 가능하도록 true로 값을 설정한다.

 

최종적으로 for문을 모두 순회하면 마지막 곡인 song_num의 cache값만 확인하면 된다.

cache[song_num][0~max_volume]를 max_volume부터 확인하여 순서대로 확인해 나간다.

만약 해당 값이 true라면 설정이 가능한 최대 볼륨을 찾은 것이고 모두 false라면 마지막 곡을 연주할 수 없으므로 -1을 출력한다.

 

#include <iostream>
#include<string.h>
using namespace std;
 
int song_num;
int start_volume;
int max_volume;
int volume_list[101];
 
int main() { 
  cin>>song_num>>start_volume>>max_volume;
 
  for(int i=1; i<=song_num ; ++i)
    cin>>volume_list[i];
 
  bool cache[101][1001];
  memset(cache , false, sizeof(cache));
 
  cache[0][start_volume] = true;
 
  int next_volume;
  for(int order=0; order<song_num ; ++order){
    for(int volume=0; volume<=max_volume ; ++volume){
      if(cache[order][volume]){
        next_volume =volume-volume_list[order+1];
        if(next_volume>=0)
          cache[order+1][next_volume] = true;
        
        next_volume = volume+volume_list[order+1];
        if(next_volume <=max_volume)
          cache[order+1][next_volume] = true;
      }
    }
  }
 
  int max_result=-1;
  for(int i=max_volume; i>=0 ; --i)
    if(cache[song_num][i]){
      max_result = i;
      break;
    }
 
  cout<<max_result<<'\n';
 
  return 0;
}

 

 

코드