[Greedy] 미적으로 아름다운 나무

• 카카오모빌리티 코딩테스트 문제 복기
• 그리디 알고리즘
• 구간 Min, Max

 

미적으로 아름다운 나무숲을 가꾸길 좋아하는 사람이 있다.

이 사람의 미적으로 아름답다는 것의 정의는 다음과 같이 '나무의 높낮이가 연속되지 않고 번갈아 나타남'으로 한다.

미적으로 아름다운 나무숲을 만들기 위해 오직 하나의 나무만을 없앨 수 있다고 하자.

나무의 높이가 정수의 배열로 주어졌을 때 아름다운 나무숲을 만들기 위한 방법의 가짓수를 구하여라.

- 아름다운 나무숲을 만들 수 없는 배열이면 -1을 리턴한다.

- 이미 아름다운 나무숲이라면 0을 리턴한다.

 

ex. [3, 4, 5, 1, 2]

1. 3을 지워서 [4, 5, 1, 2] 를 만들 수 있다.

2. 4를 지워서 [3, 5, 1, 2] 를 만들 수 있다.

3. 5를 지워서 [3, 4, 1, 2] 를 만들 수 있다.

=> 이렇게 총 세 가지 방법이 존재하므로, 3을 리턴한다.

 

조건)

- 주어진 배열에서 연속된 두 나무의 길이는 같지 않다.

- 배열 길이 조건은 ... 잘 기억이 나지 않는데, 4 ~ 1000개의 정수가 배열로 주어졌던 것 같음. (0, 1, 2, 3개인 경우도 처리하면 좋을 듯)

- 나무 높이는 최대 100으로 주어졌던 것 같다.