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

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/68646

문제 난이도

Level 3

문제 접근법

만약 풍선이 1,2,3,4,5 순서로 있다고 가정하고 해당 문제의 시뮬레이션을 돌리면 파악이 가능하다. 제일 즁요한 조건 인접할 때 = 작은값은 한 번만 터트린다 = 한 번 빼고 다 큰값만 터트린다.

1만 남을 경우: (3,4) -3인 작은 값 제거-> 나머지는 다 큰 값만 제거
이 경우는 1보다 큰 풍선값에서 인접 풍선에서 최소값을 선택하는 기회를 쓰기만 하면 다 나오는 경우다.

2만 남을 경우: (1,2) -1인 작은 값 제거-> 나머지는 2보다 큰 값만 제거
이 경우는 2보다 작은 1만 제거하면 그 외는 큰 수 이기 때문에 가능하다.

3만 남을 경우: (1,2) -2인 큰 값을 제거-> (3,4) -4인 큰 값 제거-> (3,5) -5인 큰 값 제거->(1,3) -1인 작은 값 제거-> End

4만 남을 경우: (4,5) -5인 큰 값 제거-> (2,3) -3인 큰 값 제거-> (1,2) -2인 큰 값 제거-> (1,4) -1인 작은 값 제거 -> End

5만 남을 경우: (1,2) -> (1,3) -> (1,4) -> (1,5) -1인 작은 값 제거-> End

이걸 돌려본 결과 = 제일 최소값과 본인만 남을 수 있는지에 대한 걸 check하면 혼자 남기 가능한 정수가 된다.
인접한 풍선의 입구는 양 쪽 사이드다(양쪽에서 시작할 수 있다). 그렇기 때문에 왼쪽부터 최소값과 오른쪽부터의 최소값을 구해 그 둘 중의 하나보다 작거나 같다면 그 풍선은 하나만 남을 수 있다.

통과 코드

#include <string>
#include <vector>

using namespace std;

int dp[1000001],dp2[1000001];

int solution(vector<int> a) {
	int answer = 0;
	dp[0] = a[0];
	for (int i = 1; i < a.size(); i++) {
		if (dp[i - 1] > a[i]) {
			dp[i] = a[i];
		}
		else dp[i] = dp[i - 1];
	}
	dp2[a.size() - 1] = a[a.size() - 1];
	for (int i = a.size() - 2; i >= 0; i--) {
		if (dp2[i + 1] > a[i]) {
			dp2[i] = a[i];
		}
		else dp2[i] = dp2[i + 1];
	}
	for (int i = 0; i < a.size(); i++) {
		if (a[i] <= dp[i] || a[i] <= dp2[i]) answer++;
	}
	return answer;
}

피드백

월간 챌린지할 때, 이 문제를 못 풀었다. 그래서 다른 사람 코드를 참고했다. 처음에는 set으로 풀다가 이렇게 푸니깐 통과했다. 이걸 어떻게 생각하지? 여기서 포인트는 왼쪽,오른쪽 최솟값을 구하고 그 중 하나보다 작거나 같아야하는 점이다..