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

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

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

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍

문제

수열 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 리스트에 (이전의 작은 수, 큰 수, 카운트)의 값을 넣어서 비교를 하려 했으나 마땅한 방법이 떠오르지 않았다.

 

그렇게 1시간을 넘게 고민한 끝에 결국 구글에 검색을 해 보았다.

 

해결 방법은 생각보다 단순해서 놀라웠고, 이 방법을 떠오르지 못해 스스로에게 어이가 없었다.

 

한번에 하려 하지 말고 2중 반복문을 돌리며 현재 위치와 맨 앞에서부터 비교하면서 카운트값을 수정해 가면 되는 간단한 문제였다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
  for j in range(i):
    if arr[i] > arr[j] and dp[i] < dp[j]:
      dp[i] = dp[j]
  dp[i] += 1
  
print(max(dp))

 

아래는 사용한 반례다.

6
10 20 10 30 20 50
답 4

1
1
답 1

4
5 1 2 3
답 3

6
1 5 2 6 3 4
답 4

4
1 4 2 3
답 3

5
1 4 2 3 5
답 4