백준 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
입출력
| 입력 | 출력 |
|---|---|
| 6 10 20 10 30 20 50 | 4 |
접근 방식
: 1로 초기화된 dp테이블 준비
입력받은 수열의 두번째 원소부터 볼건데, 해당 원소가 해당 원소까지의 수 중 가장 크다면 바로 전 원소의 dp값에 +1을 해서 저장. 그 외에는 바로 전 원소의 dp값과 같은 값을 저장.
dp테이블의 가장 마지막 원소를 출력 ---> 틀렸습니다.
이 방식은 이어 붙여 만들 수 있는 증가하는 다른 가능성을 차단하게됨.
알게된 점
해당 원소 이전까지의 수 중 해당 원소보다 작고, 가장 큰 길이를 구해 그 길이에 +1
가장 마지막 원소까지 증가하는 것이 아닐 수 있으므로 dp[-1]이 아닌 max(dp)를 출력.
코드
n = int(input())
nums = list(map(int, input().split()))
dp = [1]*n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[j]+1, dp[i])
print(max(dp))