[Python] 11053 - 가장 긴 증가하는 부분 수열 (실버2)

1. 문제 설명

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

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

 

---

2. 아이디어

전형적인 DP 문제.

현재 인덱스와 이전까지의 수들을 비교하며 n번 반복하는 과정에서 이동횟수는 계속 1씩 증가시킨다.

그럼 1 2 3 2 1 4 라는 input값이 들어왔을 때, 가장 긴 증가 수열은 1 2 3 4가 되어야 하는데,

계속 1씩 증가시키면 안 되는 것이 아니냐? 라고 물을 수 있지만, 1 증가 시키기 전에 당연히

증가수열 길이를 먼저 판단해주어야 한다.

1 2 3 까지는 계속 증가하겠지만, 그 다음 2가 들어오면 증가수열은 1 2 3 2 이므로 1의 이동횟수를

받아와서 그 후에 1을 증가시키면 되는 것이다.

따라서 마지막까지 이동하면 cache는 이렇게 저장된다.

i	1	2	3	2	1	6
cache[i]	1	2	3	2	1	4

따라서 3까지 이동한 횟수를 받아와서 1 증가시켜주고 cache에서 가장 큰 값을 출력시켜주면 된다. 

 

---

3. 코드

import sys

input = sys.stdin.readline

def solution():
    n = int(input())
    a = list(map(int, input().split()))
    cache = [0]*n

    for i in range(n):
        for j in range(i):
            if a[i] > a[j] and cache[i] < cache[j]:
                cache[i] = cache[j]
        cache[i] += 1
    print(max(cache))

solution()