[백준🥈2] #11053 가장 긴 증가하는 부분 수열 (Python)

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

 

✔️ Code

n = int(input())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

 

✏️ Comment

처음에 문제를 제대로 이해 못해서 복잡하게 생각하고 있었다...

1. 뒤의 숫자가 앞의 숫자보다 큰지
2. 뒤의 dp 값이 앞의 dp 값보다 작은지

두 가지를 검사해서 뒤에 나오는 숫자가 앞의 숫자보다 크고 dp값이 작으면 dp[i] 에 dp[j] 값을 저장해준다.
여기서 dp 값은 증가 부분 수열에 해당되는 숫자들의 개수이다. (이게 많은 경우를 구해야 하는 것)
즉, 자기 자신보다 작은 숫자들 중 가장 큰 길이를 구하고 그 길이의 값에 1을 더해주면 된다.

문제 풀 때도 헷갈렸는데..... 글로 풀어쓰려니 더 헷갈린다. dp에서 많이 좌절하고 있는 중이다 ^0^