https://www.acmicpc.net/problem/14002
14002번: 가장 긴 증가하는 부분 수열 4수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net
바로 전에 풀었던 가장 긴 증가하는 부분 수열처럼, 길이는 걍 DP돌려서 풀면 된다.
근데 어떻게 수열을 하나씩 출력할까?
나는 b를 각각 입력값에 대해[0,1]로 만들었다.
첫번째 원소에는 이 원소를 끝으로 하는 가장 긴 수열
두번째 원소에는 가장 긴 수열에서의 이 원소 바로 이전 원소를 넣는다.
출력형식에 따라 가장 긴 수열을 출력하고,
정답을 입력할 리스트를 만들고, 가장 긴 수열의 끝 a[b.index(max_b)] 원소를 넣는다.
이후, b[i][1] 의 원소가 -1이 아니라면, a[b[i][1]]이 바로 그 전 숫자이고,
-1이라면, 수열의 시작이다.
-1이 나올때까지 반복하면, 리스트는 수열의 끝에서 수열의 시작까지 차례데로 담겨있게 될 것이고,
이를 출력형식에 따라 reverse()한뒤 출력해주면 된다.
근데 다른사람들 풀이를 보니깐 그냥 1차원 배열을 선언하고, 만일 수열의 최대 길이가 4라면, 왼쪽으로 탐색하면서 그 다음 수열이 3,2,1이 되도록 선언해서 풀었다.
내 코드가 푸는시간은 더 짧긴 한데, 코드량이 2배많다.
n=int(input())a=list(map(int,input().split()))b=[[0,-1] for _ in range(n)]
for i in range(n): max_a=0 #최댓값 last_num=-1 #이전숫자
for j in range(i): #a[i]전까지 a[i]보다 작은수 비교 if a[j]<a[i]:
if b[j][0]>max_a: max_a=b[j][0]
last_num=j b[i]=[max_a+1,last_num] #[i까지의 최대길이, i이전의 수]
answer=max(b)print(answer[0]) #여기서 배열 최댓값 반환
first_num=a[b.index(answer)]tmp=answer[1]ll=[first_num]while True:
if tmp==-1:break ll.append(a[tmp]) tmp=b[tmp][1]
ll.reverse() print(* ll)