[백준] 11053 - 가장 긴 증가하는 부분 수열

문제

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하라.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 

최장 증가 부분 수열

이런 문제는 일반적으로 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 문제라고 하는데, 동적 계획법으로 풀어낼 수 있는 유명한 알고리즘 풀이다.

 

최장 증가 부분 수열이란 임의의 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분 수열 중 오름차순으로 정렬된 가 장 긴 수열을 의미한다.

예로 들어, 주어진 수열이 3 5 7 9 2 1 4 8이라고 하자. 이 수열은 다음과 같은 부분 수열을 만들 수 있다.

• 3 7 9 1 4 8 : 일부가 오름차순
• 7 9 1 8 : 일부가 오름차순
• 3 5 7 8: 전체가 오름차순
• 1 4 8 : 전체가 오름차순

여기서 일부 또는 전체가 오름차순인 수열을 증가 부분 수열이라고 하며, 증가 부분 수열 중 가장 긴 수열은 최장 증가 부분 수열이라고 한다. 즉, 위 수열에서 부분 수열 3 5 7 9 또는 3 4 7 9가 최장 증가 부분 수열에 해당한다.

 

동적 계획법을 활용해 문제를 해결할 때는 테이블에는 자기 자신을 포함한 증가 부분 수열의 최대 길이를 저장한다.

즉, i 번째 이전에 위치하고 i 번째 수보다 작은 수 중 테이블 값이 최대인 수를 찾아야 한다.

 

 

풀이

다음과 같이 구현했다.

 

1. 입력 값 초기화

A = int(sys.stdin.readline())
A_i = list(map(int, sys.stdin.readline().split()))

 

2. 테이블 업데이트

dp = []
for i, a in enumerate(A_i):
    # i 번째 이전 수 중 그 값이 i 번째 값보다 작은 수의 리스트
    #  단, 해당 수의 테이블 값을 참조한다.
    tmp = [dp[i] for i, v in enumerate(A_i[:i]) if v < a]
    # 리스트의 최대값 계산
    val = max(tmp) if tmp else 0
    # 테이블에 i번째 수를 포함한 수열의 길이 저장
    dp.append(val + 1)

 

3. 결과 출력

print(max(dp))

 

 

참고 문서

[백준 14003] 가장 긴 증가하는 부분 수열 5

BAEKJOON#11053 가장 긴 증가하는 부분 수열