[Programmers] 풍선 터트리기

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

그리디 하게 생각해야 하는 알고리즘이었습니다.

 

알고리즘은 아래와 같습니다.

1. 문제 조건 중 "인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다."라는 조건이 있습니다.

1.1 따라서, 양 쪽 끝 풍선은 어떠한 경우에도 터트릴 수가 있습니다.

2. 1번부터 n-1번 풍선까지는 왼쪽 구간의 최솟값 혹은 오른쪽 구간의 최솟값보다 작을 경우 터트릴 수 있습니다.

2.1 1번의 조건에 의하면 왼쪽 구간의 최소값보다 작고 오른쪽 구간의 최소값보다 크더라도 터트릴 수 있고 왼쪽 구간의 최소값보다 크고 오른쪽 구간의 최소값보다 작더라도 터트릴 수 있습니다.

3. 1.1과 2번을 통해 구한 터트릴 수 있는 풍선의 수를 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~