동적계획법. [11055]

[1. 문제 설명]

https://www.acmicpc.net/problem/11055

---

[2. 풀이 접근]

구현의 편의 상 배열은 1부터 시작하도록 한다.

 

LIS 를 구하기

• 현재 값에서 다음 값을 선택하는 경우는 현재 index 를 기준으로 자신 보다 더 클 때만 선택 할 수 있다. 

최적부분구조

• i < j 에서, j 부터 시작하는 LIS 를 한번 구하면, 이는 재사용 할 수 있다.
• j 부터 수열이 시작하므로, j 이전에 어떤 값이 오더라도 그 선택에 영향을 주지 않기 때문이다.

재귀적 동적계획법과 반복적 동적계획법 모두 풀이가 가능하다.

• 반복적 동적계획법 풀이 시, 계산 순서(방향) 은 앞->뒤, 뒤->앞 으로 하도록 한다.
• i < j 에서, cache[i] 를 구할 때 cache[j] 가 아직 최적화가 안 되었기 때문이다.

합이 가장 큰 LIS 의 원소 구하기

• 문제에서 요구하는 사항은 아니지만, 생각해볼만한 문제이다.
• 재귀적 동적계획법 풀이 기준으로, 각 단계에서 최대 값이 갱신되는 순간에 주목한다.
• 이 순간에, 현재 index 에서 다음 index 를 가리키는 테이블을 업데이트 한다.
• LIS 종료 후, index 테이블을 이용하여 합이 최대 인 LIS 를 출력하도록 한다. 

---

[3. 코드 - 재귀적]

 

[3. 코드 - 반복적]