2: https://www.acmicpc.net/problem/12015 3: https://www.acmicpc.net/problem/12738 4: https://www.acmicpc.net/problem/14002 5: https://www.acmicpc.net/problem/14003
- 2월동안 187문제 풀기(지난달 누적 87개) (48/187)
- 일단 2번과 3번은 쉽다. 그냥 LIS 풀듯이 풀면 된다.
- 문제는 4번과 5번 출력을 해주어야 하는 부분이다.
- 처음에는 어줍잖게 $O(NLogN)$으로 찾은 dp 배열을 이용해서 풀려고 했는데, 안일한 생각이었다.
7 / 4 5 6 7 1 2 3
으로 입력이 들어오면 망한다.- 위의 예에서 LIS는
1 2 3 7
일텐데 여기서 이미 망가져버린1 2 3
을4 5 6
으로 되돌릴 계제가 없다. - 결국 다른 DP에서 복원할 때 하듯이, 중간 결과를 포인터로 저장해놓는 식으로 풀어야한다.
1 |
|