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

<문제>

링크 : https://www.acmicpc.net/problem/11053

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

---

<코드>

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

count = [1] * N
for i in range(1, N):
    _list = []
    for j in range(i):
        if A[i] > A[j]:
            _list.append(j)
    if len(_list) ==0:
        count[i] = 1
    else:
        _x = count[_list[0]]
        for _i in range(len(_list)):
            index = _list[_i]
            _x = max(count[index], _x)
        count[i] = _x+1
M = max(count[i] for i in range(N))
print(M)

---

<풀이>

한번에 입력된 배열에 대해 가장 긴 증가하는 수열을 찾을 수 없다.

배열의 앞에서 부터 오른쪽으로 이동하면서 가장 긴 수열의 길이를 저장하여 배열의 부분 최적해를 통해 전체 문제의 최적해를 구해야 한다.

index를 1씩 증가시키면서 해당 index 앞의 가장 긴 수열의 길이에 +1을 해주도록 한다.

예를 들어, index가 4일때 앞선 배열의 원소가 index가 4인 배열의 원소보다 작고 그 원소까지 계산한 배열이 가장 긴 원소를 선정한다. 그 원소가 가진 배열의 길이 +1을 해준 값이 index가 4인 원소에서의 가장 긴 증가하는 수열의 길이가 된다.

---

 

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/11053

GitHub - Junuux/Algorithm