백준 문제 중 14002번, DP, ‘가장 긴 증가하는 부분 ‘
풀이
백준 문제 중 14002번
https://www.acmicpc.net/problem/14002
문제
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.
이전에 다뤘던 가장 긴 증가하는 부분 수열 와 유사하나 부분수열을 직접 출력해야한다
어떻게 부분수열 추적을 구현하기가 조금 까다로웠다.
Try1
문제의 조건을 이용해 추적
dp의 원소를 역순으로 스캔 하는데 max(dp)를 m이라고 할때 m과 일치하는 인덱스 i를 찾고 i를 idx에 저장한다. 그 다음은 m-1과 일치하는 dp[i]를 찾고 i를 idx이 저장한다. 이러한 과정을 m이 1이 될때까지 반복한다. 가장 긴 부분수열이
여러가지일 경우 아무거나 출력해도 된다는 조건이 있으므로 같은 m값을 가진 dp의 원소가 여러개 있어도 신경쓰지 않아도 된다.
그저 순서대로 인덱스를 찾기만 하면 된다. 이후 역순으로 저장된다 idx를 뒤집고 a[idx]를 차례로 출력하면 된다.
n = int(input())
a = list(map(int,input().split()))[:n]
dp = [1]*n
for i in range(n):
for j in range(i):
# a[i]가 a[j]보다 클때만 부분수열이 늘어날 수 있음
if a[j]<a[i]:
# dp[0~i-1]까지의 수 중 최댓값 +1 을 최장 부분수열로 판단
dp[i]=max(dp[i],dp[j]+1)
m = max(dp)
ans = []
# dp[n]부터 dp[0]까지 스캔중에 m과 같은 dp[i]를 만나면
# a[i]를 ans에 저장
for i in range(n-1, -1, -1):
if dp[i]==m:
ans.append(a[i])
m-=1
print(m)
# 역순으로 출력
ans=ans[::-1]
for i in ans:
print(i, end=' ')
6
10 20 10 30 20 50
0
10 20 30 50
Try2
직전 부분수열을 저장
조금더 직관적인 방법으로 부분수열을 직접 저장해 구해봤다.
비슷하지만 조금 다른 부분이 있다. a[j]<a[i]와 dp[j]+1<dp[i]를 동시에 만족할때 부분수열을 판단한다. 풀어 말하면 a[i]가 a[j]보다 큼과 동시에 j의 부분수열의 길이가 1만큼만 크다면 a[i]또한 a[j]에 가능한 최장 부분수열에 더할 수 있다는 뜻이다.
a[i]를 a[j]의 최장 길이 부분수열 즉 ans[j]에 합해주고 그 값을 a[i]에 저장하고, dp[i]를 최신화 한다.
n = int(input())
a = list(map(int,input().split()))[:n]
dp = [1]*n
ans = [[i]for i in a]
for i in range(n):
for j in range(i):
# a[j]<a[i]일때 최장 부분수열이 늘어 날 수도 있고
# 동시에 dp[j]+1>dp[i]를 만족한다면 a[i]또한 ans[j]+a[i]도 부분수열이 된다.
# a그러므로 ns[i] 에 [*ans[j],a[i]]을 저장한다.
if a[j]<a[i] and dp[j]+1>dp[i]:
ans[i] = [*ans[j],a[i]]
dp[i] = dp[j]+1
print(max(dp))
# ans를 길이순으로 정렬
ans.sort(key=len)
# 최장길이에 해당하는 부분수열 출력
for a in ans[-1]: print(a,end=' ')
6
10 20 10 30 20 50
4
10 20 30 50
Leave a comment