동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)

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

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

##### 문제 #####
# 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
# 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 
# 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

##### 입력 #####
# 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
# 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

##### 출력 #####
# 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

▶ 접근 방법

이분 탐색으로 풀었던 문제였는데 이번에는 동적 프로그래밍으로 해결하였다.

우선, 입력 받은 수열의 크기만큼 DP 테이블을 만들어준다.
이후 전체 수열 리스트에서 하나 씩 숫자를 꺼낸다.
이때 꺼낸 숫자가 이전 숫자보다 크다면 DP 테이블을 업데이트해준다.

인덱스를 어떻게 사용하는지가 관건인 문제였다.

 

▶ 풀이 코드

import sys

N = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().split()))
DP = [1 for _ in range(N)]
# print(numbers, DP)

# numbers의 1번 째 인덱스부터 하나씩
for i in range(1, N):
    # 확인하려는 인덱스 이전 인덱스까지의 모든 값들을 비교해본다.
    for j in range(i):
        # 확인하려는 인덱스의 값이 이전 인덱스의 값보다 크다면
        if numbers[i] > numbers[j]:
            # DP 테이블을 업데이트 해준다.
            DP[i] = max(DP[i], DP[j] + 1)

print(max(DP))

 

▶ 관련 링크

2021.11.25 - [알고리즘] - 동적 프로그래밍(Dynamic Programming)이란?

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 피보나치 수 2(백준 2748번)

2021.11.25 - [알고리즘] - 동적 프로그래밍 : 01타일(백준 1904번)

2021.11.26 - [알고리즘] - 동적 프로그래밍 : 평범한 배낭(백준 12865번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 동전(백준 9084번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : LCS(백준 9251번)

2021.11.27 - [알고리즘] - 동적 프로그래밍 : 가장 긴 증가하는 부분 수열(백준 11053번)