[백준] 14002번: 가장 긴 증가하는 부분 수열 4

코딩테스트/백준

yjseo01 2023. 11. 10. 13:11

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

solved.ac 잔디에 구멍 뚫렸길래 그냥 마음 편하게 시험공부나 하자 싶어서 며칠 안풀고 놀았더니 되게 오랜만에 푼 것 같다..ㅋㅋㅋㅋ

증가하는 부분 수열을 구하는 방법은 쉽게 떠올렸지만, 이걸 어떻게 역추적해서 출력해야할지 잘 감이 오지 않아서 풀이를 찾아봤다.

dp[k]를 arr[k]까지의 증가하는 가장 긴 수열의 길이라고 했을 때,

증가하는 가장 긴 수열의 가장 큰 숫자의 인덱스를 저장하고,

이를 하나씩 줄여가면서 dp와 비교를 하면 역추적할 수 있는 것 같다.

참고
14002번 풀이: https://cocoon1787.tistory.com/455