[백준 11053 파이썬] 가장 긴 증가하는 부분 수열 (실버2, 다이나믹 프로그래밍)

알고리즘 유형 : 다이나믹 프로그래밍
풀이 없이 스스로 풀었나요? : ❌

---

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

솔루션

n이 1이면 가장 긴 증가하는 부분 수열의 길이는 1이므로 res, dy[1]를 1로 초기화한다.

n이 2 이상이면 2중 for 문으로 arr[2] ~ arr[n] 값들과 그 이전 값들과 비교하여 dy에 최댓값을 저장한다.

소스 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    arr.insert(0, 0) # 인덱스를 맞추기 위해 설정
    dy = [0] * (n + 1)
    res = dy[1] = 1 # 한개만 입력되면 가장 긴 증가하는 부분 수열의 길이는 1이므로 res, dy[1]를 1로 초기화
    for i in range(2, n + 1):
        max = 0
        for j in range(i - 1, 0, -1):
            if arr[j] < arr[i] and dy[j] > max:
                max = dy[j]
        dy[i] = max + 1
        if dy[i] > res:
            res = dy[i]
    print(res)

---

후기

n==1일 때를 고려하지 않고 res=0으로 초기화해 계속 실패하여 많은 시간을 소요했다.