[BOJ/Step15] 11053 : 가장 긴 증가하는 부분 수열 (Python)

www.acmicpc.net/problem/11053

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

---

1. 입력받은 수들을 리스트 seq에 저장

2. seq와 같은 길이의 t_seq를 생성하고 첫번째 요소는 1, 나머지는 0으로 채운다

    => seq[n]까지의 가장 긴 증가하는 부분 수열의 개수를 리스트 t_seq[n]에 저장할 것

3. for문으로 t_seq[1] ~ t_seq[n-1] 까지 계산

    => 가장 긴 수열에는 seq[n]가 포함될 것이기 때문에 seq[n]가 가장 큰 수가 될 것이다

    => seq[n] 이전의 seq[n]보다 작은 숫자들 중 t_seq[n]가 가장 큰 숫자에 1을 더해 저장한다

  3-1. 리스트 a에 0을 저장

  3-2. for문으로 a에 seq[0] ~ seq[n-1] 중 seq[n]보다 작은 숫자들의 t_seq[n]을 저장

  3-3. a의 최댓값 + 1을 t_seq[n]에 저장

4. t_seq의 최댓값을 출력

 

# 11053.py

n = int(input())
seq = [i for i in map(int, input().split())]
t_seq = [1] + [0 for _ in range(n-1)]

for i in range(1, n):
    a = [0]
    for j in range(i):
        if seq[j] < seq[i]:
            a.append(t_seq[j])
    t_seq[i] = max(a) + 1

print(max(t_seq))

 

이제 뭔가 DP를 어떤 방식으로 풀어야 하는지 알 것 같은 느낌이다..