알고리즘 유형 : DP, 최단경로 역추적
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/14002
SOLVE 1
메모이제이션 리스트에 최단경로도 담아서 같이 갱신해나가는 풀이
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
LIS = [[1, ""] for _ in range(N)]
LIS[0][1] = str(A[0])
for cnt in range(1, N):
selected = cnt
for prev in range(cnt):
if A[cnt] > A[prev] and LIS[cnt][0] < LIS[prev][0]+1:
LIS[cnt][0] = LIS[prev][0]+1
selected = prev
LIS[cnt][1] = LIS[selected][1] + " " + str(A[cnt])
length, arr = max(LIS)
print(length, arr, sep="\n")
SOLVE 2
LIS를 구하고, 최단경로를 따로 구하는 풀이
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
LIS = [1]*N
for cnt in range(1, N):
for prev in range(cnt):
if A[cnt] > A[prev]:
LIS[cnt] = max(LIS[cnt], LIS[prev]+1)
order = max(LIS)
print(order)
result = []
for idx in range(N-1, -1, -1):
if LIS[idx] == order:
result.append(A[idx])
order -= 1
print(*result[::-1])SOLVE 1) 풀이 요약
- LIS 알고리즘으로 풀 되, 최단 경로를 구하는 약간의 로직을 추가하면 된다.
-
LIS 리스트의 원소로 길이 값과 최단 경로 문자열을 같이 갖는다.
현재 순회 원소 index인 cnt에 대해, LIS 알고리즘대로 cnt 이전의 인덱스까지 for로 돌면서 A[cnt]가 A[prev]보다 큰 prev를 찾고, 만약 LIS 값이 갱신돼야하면 갱신하고 그 때의 index를 selected에 담아둔다.
cnt 이전의 모든 인덱스에 대해 비교&갱신하고나서, 최종적으로 갱신된 index가 담긴 selected에 대해 LIS[cnt]의 최단 경로 문자열을 LIS[selected]의 최단 경로 문자열 + A[cnt]로 갱신해준다.
SOLVE 2) 풀이 요약
- 길이 값을 LIS 알고리즘을 통해 구해준다.
-
만약 구한 LIS 값이 K라고 하자. 이 때 LIS 리스트에는 반드시 LIS 값이 1, 2, 3, ..., K인 원소들이 있다. 왜냐하면 LIS 값은 이 전에 미리 구해놓은 값들에 +1을 해서 갱신해주기 때문에, 초기값 1부터 시작해서 K까지 모든 값이 LIS에 존재한다.
따라서, LIS 리스트의 오른쪽부터 시작하여, 값이 K, K-1, ..., 2, 1인 idx를 차례대로 구해줘서 그 idx에 해당하는 A 리스트의 원소를 result에 붙혀나가면 최단 경로가 최종적으로 완성될 수 있다.
배운 점, 어려웠던 점
- LIS 알고리즘을 어떻게 쓰는건지 까먹었다... 나중에 꼭 이때까지 공부한 내용 복습하고 SW마에스트로 시험치러 가야겠다.
