[프로그래머스 LV3] 풍선 터트리기 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/68646

프로그래머스

 

워.. 정말 어려운 문제였다. 감도잡히지 않았다..!

 

먼저 처음엔 DP인가 싶었지만 

 

1 2 3 4 5 에서 1 2를 선택했을 때의 결과는 1 2 4 5 에서 1,2를 선택했을 때의 결과와 아주 달라진다. 그리고 전체 시뮬레이션을 돌리는 것은 어려운 것은 아니지만 당연히 시간초과가 발생할만한 N의 크기였다.

 

그래서 이 문제의 해결법은 먼저 작은 단위에서 생각해보는 것이다.

 

가운데를 기준으로

4가지 경우의 수를 생각해볼 수 있다. 

1. 가운데 수가 양 옆 보다 클 경우 -> 1 3 2

 

1, 3 을 선택 -> 한번은 작은 것을 지울 수 있으므로 3

3 2 를 선택 -> 이미 작은 것을 지웠으므로 큰 것을 지워야함

 

살아남을 수 없다.

 

2. 오름차순일 경우 -> 1 2 3

1, 2 선택 -> 한번은 작은 것을 지울 수 있으므로 2 3

2, 3 선택 -> 2

 

살아남는다.

 

3. 내림차일 경우 -> 3 2 1

 

오름차와 마찬가지로 살아남는다.

 

4. 가운데 수가 양 옆보다 작을 경우 -> 2 1 3

2, 1 선택 -> 1 3

1, 3 선택 -> 1

 

살아남는다.

 

N = 3 일 때는 간단하게 비교할 수 있지만 10 0 8 1 2 3 4 5 6 처럼 N이 증가한다면 1 3 5 가 올지, 10 3 6이 올 지 알 수없다.

하지만 우리는 위의 규칙을 찾아냈다. 그리고 기준값에서 오른쪽, 왼쪽을 작은수사용 규칙을 사용하지 않고 지우기를 사용한다면 양 쪽의 최소값이 남게 된다.

 

기준이 2라고 하면

 

0 2 3 이 남는다는 뜻이다. 그리고 이 N = 3으로 만들고 나서 위 규칙을 사용한다. 작은수 지우기 규칙을 사용하지 않았기 때문에 위 규칙을정확히 사용가능하다. 그렇다면 이런 반론을 제기할 수 있다.

 

2 3 1 처럼 살아남을 수 없는 규칙이지만, 만약 작은수 지우기를 사용해서 2 3 4가 올수도 있지 않나?

 

그럴수도 있다! 하지만 2 3 4 규칙도 결국 작은 수 지우기 규칙이 필요하기 때문에 결국 살아남지 못하는 것은 똑같다.

 

규칙을 찾고 이 규칙이 수를 늘려도 만족하도록 상황을 바꾸는 것이 요구되는 매우 까다로운 문제였다고 생각한다. 

 

도움을 받은 블로그 : https://g-egg.tistory.com/92 

[Programmers] 풍선 터트리기 (Java)

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<int> a) {
    int answer = 2;
    int left[a.size() + 1];
    int right[a.size() + 1];
    
    int minValue = 1000000001;
    
    for(int i = 0; i < a.size(); i++){
        if(minValue > a[i]){
            minValue = a[i];
        }
        
        left[i] = minValue;    
    }
    
    minValue = 1000000001;
    
    for(int i = a.size() - 1; i > -1; i--){
        if(minValue > a[i]){
            minValue = a[i];
        }
        
        right[i] = minValue;
    }
    
    for(int i = 1; i < a.size() - 1; i++){
        if(a[i] > left[i - 1] && a[i] > right[i + 1]) continue;
        
        answer++;
    }
    
    return answer;
}