[25.03.18] algo 백준 12762 리뷰

25.03.18(Tue) 알고리즘 스터디 리뷰

문제 요약

• 롤러코스터 기둥의 높이가 주어질 때, 하이라이트 구간을 최대한 길게 만들고자 합니다.
• 하이라이트 구간은 내리막을 쭉 내려왔다가 다시 올라오는 구간입니다.
• 일부 기둥을 제거할 수 있지만, 최대한 많은 기둥을 남기는 것이 목표입니다.
• 롤러코스터의 진행 방향은 공사 후 결정되므로, 양방향 모두 고려해야 합니다.
• 연속적으로 높이가 같은 기둥은 없어야 합니다.
• 하이라이트 구간이 불가능한 경우 가장 높은 기둥만 남깁니다.
• 올라오는 구간은 없을 수도 있습니다(즉, 내리막만 있어도 됨).

풀이방식

수열을 입력받았을때 롤러코스터가 생성될수 있는 모양은 V, ↘, ↗ 세가지 모양이고 이때 가장 낮은 점을 기준으로 양쪽으로 LIS를 구한다음에 중복되는 부분을 제외하는 방식으로 풀 수 있었다. 기본적인 아이디어는 이러하지만, 하나의 index를 기준으로 양쪽 LIS를 구하고 index값 하나를 빼주면 되는 문제였다. 여러번의 시도 끝에 틀렸었는데 LIS를 양쪽으로 하고 무조건 들어가는 중복을 제거를 제대로 하지 못해서 문제가 생겼다.

결과 코드