백준 1495 기타리스트, c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 틀렸다는 결과가 나왔다.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, start_v, max_v;
    cin >> n >> start_v >> max_v;
    
    int v[n];
    for(int i=0; i<n; i++)
        cin >> v[i];
    
    for(int i=0; i<n; i++){
        if( max_v < (start_v+v[i]) ) { //볼륨 못 올리는 경우
            if( (start_v-v[i]) < 0 ) { //볼륨 못 내리는 경우, 종료
                start_v = -1;
                break;
            }
            else { //볼륨 내리기
                start_v = (start_v-v[i]);
            }
        }
        else if( (start_v-v[i]) < 0 ) { //볼륨 못 내리는 경우
            if( max_v < (start_v+v[i]) ) { //볼륨 못 올리는 경우, 종료
                start_v = -1;
                break;                
            }
            else { //볼륨 올리기
                start_v = (start_v+v[i]);
            }
        }
        else{ //볼륨 올리기 내리기 다 가능한 경우
            if( abs(max_v-(start_v+v[i])) > abs((start_v-v[i])) ){ //비교해 볼륨 올리기
                start_v = (start_v+v[i]);;
            }
            else{ //비교해 볼륨 내리기
                start_v = (start_v-v[i]);
            }
        }
    }
    
    cout << start_v;
    return 0;
}

 

 

 

위의 방식으로 간단한 예제는 통과 되지만, 정말 모든 조건을 고려해주기 위해서는 모든 경우를 시도해서 가장 최적의 값을 내야 한다.

그렇게 모든 조건을 고려해주기 위해서는 동적계획법으로 구현해야 했다.(dp배열 사용) 

동적계획법은 이렇게 모든 조건을 (트리 구조처럼) 생각해 주어야하는데, 효율적으로 간단하게 구현해야 하는 경우에 많이 사용하는 것 같다.