BOJ-11053 가장 긴 증가하는 부분 수열

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

문제 소개

수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구한다.

문제 풀이

dp로 풀이하였다.

n은 입력받을 수열의 길이이며 arr은 수열이다.

리스트 dp는 딕셔너리를 n개 가지며, dp[n]은 arr[0] 부터 arr[i]까지 확인했을 때 만들 수 있는 수열들의 정보를 담는다.

예를 들어 아래와 같이 입력이 주어질 때

6
10 20 10 30 20 50

dp[3][30]은 30까지 확인했을 때 만들 수 있으면서 30으로 끝나는 수열 중 가장 긴 수열이다.

반복문을 통해 딕셔너리들의 key와 value들을 비교하며 업데이트하여 값을 얻을 수 있었다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

n = int(input())
arr = list(map(int, input().split()))

dp = [dict() for _ in range(n)]
# 초기값 할당
dp[0][arr[0]] = 1

for i in range(1, n):
    # 이전 단계의 key와 value를 토대로 반복
    for j in dp[i - 1].items():
        # 이전 단계에 있던 key가 없다면 같은 value로 추가
        if j[0] not in dp[i]:
            dp[i][j[0]] = j[1]

        # key가 arr[i]보다 크다면
        if arr[i] > j[0]:
            # arr[i]로 끝나는 수열이 하나도 추가되지 않았거나 더 큰 수열을 찾은 경우
            if arr[i] not in dp[i] or dp[i][arr[i]] < j[1] + 1:
                dp[i][arr[i]] = j[1] + 1

        # key가 arr[i]보다 같거나 작다면
        else:
            # arr[i]로 끝나는 수열이 추가되지 않은 경우에만
            if arr[i] not in dp[i]:
                dp[i][arr[i]] = 1

print(max(dp[-1].values()))