20.06.15 개발일지 - 가장 긴 증가하는 부분 수열

RedChiken 2020. 6. 15. 22:10

2020. 6. 15. 22:10

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

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

www.acmicpc.net

문제 항목이 Dynamic Programming이라 어떻게 연산을 할까 고민하다가 뒤에서부터 연산하는 방식을 생각했습니다.

먼저 각 index는 부여된 값과 더불어 index와 sublength를 가지고 있습니다.

index는 해당 위치 다음에 올 index, sublength는 자신 뒤의 수열의 길이를 뜻합니다.

index와 sublength는 기존 수열의 역순으로 연산을 합니다.

자신의 뒤 숫자의 값이 자신보다 크거나 같을 때, sublength와 index 값을 저장합니다.

단, 같은 조건에서는 숫자의 값이 작은 것이 우선권을 가집니다.

이런 식으로 구현을 하는데 제시된 예시는 해결하나 추가로 생각한 예시를 해결하지 못했습니다.

뒷 숫자와 이어지지 않는 경우를 먼저 탐색하지 못 해서 문제가 생기는 것으로 예상되며,

내일 이 문제를 해결해보려 합니다.

치킨 날다