[ICPC 본선 대비 뇌셋] Day 11

백준 15599번 Ascending Photo

수열을 증가하는 순서대로 만들려면 얼마나 잘라야 하는가를 묻는 문제이다. 이메이미와 탐레프는 1500바이트 선에서 정리했는데, 나는 4000바이트 코드 말고는 어떻게 짜야하는지 잘 모르겠다.

감소하는 부분이 있으면 무조건 잘라야한다. 따라서 전처리를 하여 m개의 부분연속수열들로 쪼갠다. 편의상 모든 숫자는 1부터 n까지 나타난다고 하자.

같은 숫자가 붙어있으면 그 사이를 자를필요가 없으므로, 이것 또한 전처리로 묶어 각 부분수열을 순증가하는 수열로 만들자. 또한, 여기에서 

이때, 이 부분수열들을 잘라서 원래의 수열을 만든다고 생각해보자. 원래 수열에서 a와 a+1이 연속해서 나타나는 경우만 집중적으로 보자. 만약 어떠한 부분수열에서 a와 a+1이 연속해서 나타난다면, 이 경우는 a와 a+1사이를 자르지 않아도 될 것이다. 물론 원래 수열에서 a, a+1이 연속해서 나타나는 부분은 한번이므로, 최대 한번을 절약할 수 있다. 한편, 어떤 부분수열에서 a, a+1을 자르지 않는다고 결정한다면, 같은 부분수열에서 a+1, a+2 또는 a-1, a는 무조건 잘라야한다.(사실 그게 아닌 경우가 하나 있다. a, a+1, a+2가 연속해있고, a+1이 하나밖에 없으면 둘다 안잘라도 된다.) 이것을 잘 고려해서 추가적으로 안잘라도 되는 길이를 dp를 통해서 선형시간만에 구할 수 있다.

근데 이렇게 짜면 코딩이 조올라 빡셀거같다. 더 단순화시킬 수 있을거같은데 잘 모르겠다. 다시 멍청해졌나ㄹㅇㅋㅋ

[시간복잡도] O(NlgN)