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

1. 문제 설명

문제링크

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 수열의 크기
N = int(input())

# 리스트 선언
lst = list(map(int, input().split()))

# N개 길이 만큼 리스트 1로 선언 1로 선언하는 이유는 모든 부분 수열은 본인 혼자만 들어가 있을수도 있기때문에 1로 선언
DP = [1] * N

for i in range(N):
    for j in range(0, i + 1):
        # 본인차례 이전 에 모든 숫자 들을 비교
        if lst[i] > lst[j]:
            # 기존의 길이 즉 이미 포함된 숫자들을 포함 시키지 않기 위해 max 메서드를 통해 길이 비교
            DP[i] = max(DP[i], DP[j] + 1)
# 출력
print(max(DP))

3. 회고

Q. 문제를 보고 든 생각

• 10달전 처음 이 문제를 보고는 이중 반복문이면 풀리 겠네!! 하면서 엄청 쉽다는 식으로 도전하곤 했었다.
• 하지만 이 문제를 이중문으로 풀게 되면 시간 초과를 맞게 되는 결과가...ㅠㅠㅠㅠ
• 결국 알고리즘 분류를 보게 되었고 다이나믹 프로그래밍(DP) 이라는 것을 알게 되었고
• 구글링을 통해서 DP를 학습한 이후에 풀리게 된 문제이다

4. 아쉬운 점 혹은 고쳐야 할점

조금더 좋은 풀이가 있다면 댓글로 알려주세요