- Problem Link : https://www.acmicpc.net/problem/14002
문제
수열 A가 주어졌을때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 수열 A의 크기가 주어진다.
- 둘째 줄, 수열 A를 이루고 있는 원소가 주어진다.
출력
- 첫째 줄, 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
- 둘째 줄, 가장 긴 증가하는 부분 수열을 출력한다.
풀이
백준 11053번을 풀고 이 문제를 풀어보면 쉽게 풀 수 있다. 기존 11053번을 풀때 다이나믹 프로그래밍 기법으로 현재 i번째 원소에는 i번째 원소를 마지막 원소로 하는 부분 수열의 길이로 구현했다. 그렇게 진행해가면서 최대 길이를 미리 저장해놓았다가 마지막에 최대 길이만 출력하는 아래와 같은 코드로 구현했다.
11053번
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * (n)
ans[0] = 1
for i in range(1, n):
max_len = 1
for j in range(i, -1, -1):
if a[j] < a[i]:
if ans[j] + 1 > max_len:
max_len = ans[j] + 1
ans[i] = max_len
print(max(ans))14002.py
이 문제가 11053번 문제와 다른 점은 길이 뿐만 아니라 부분 수열까지 출력해달라는 점이다. 따라서 ans에 이번엔 길이가 아니라 a[i]를 마지막 원소로 하는 최대 길이의 부분 수열이 들어가도록 조정했다.
i번째 부분 수열을 아래와 같은 과정으로 구한다.
- 앞에 있는 부분 수열들을 모두 방문하면서 마지막 원소가 a[i]보다 작은 수열을 찾는다.
- a[i]가 마지막에 들어갈 수 있는 수열들
- 그 수열들 중 길이가 제일 긴 부분 수열을 선택해 해당 부분 수열에 a[i]를 넣은 값을 저장한다.
- 이 때 정답에서 최대 길이와 부분 수열을 원하기 때문에 방금 넣었던 수열의 길이를 비교해 최대보다 크다면 해당 부분 수열과 길이를 기억하고 있다가 마지막에 출력해준다.
아래 코드를 보면 알겠지만 이 때 우리가 원하는 모든 부분 수열 중 최대 길이는 ans_len이라는 변수에 최대 길이의 부분 수열은 ans_list에 저장되는 것을 확인할 수 있다.
길이 대신 수열을 유지한다는 점에서만 차이가 있고 실제 작동 원리는 11053번 문제와 차이는 크게 없다.결국 해당 문제를 앞의 부분 수열들을 모두 반복하면서 자신이 들어갈 수 있는 모든 수열 중 길이가 제일 긴 수열에 자신을 추가시켜 기존 결과에 추가하면서 진행하는 방식이다.
- 기존의 결과를 저장해두고 추후 계산에 이용하는 전형적인 다이나믹 프로그래밍 기법이다.
시간 복잡도를 계산하면 결국 n개의 원소에 대해 자신보다 작은 부분 수열들을 모두 방문하기 때문에 O()이며 입력 값이 많아지면 시간 초과 오류가 발생할 확률이 높다. 실제 아래 비슷한 문제 중 가장 긴 증가하는 부분 수열 2 문제는 수열의 크기가 1,000,000까지 가능하므로 이 문제 풀이 그대로 풀면 시간 초과가 발생한다. 한 번 직접 풀어보면서 시간 복잡도를 줄여보도록 하자.
코드
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [[a[0]]]
ans_max = 1
ans_list = [a[0]]
for i in range(1, n):
max_len = 1
max_list = [a[i]]
for j in range(i - 1, -1, -1):
if ans[j][-1] < a[i]:
if len(ans[j]) + 1 > max_len:
max_list = ans[j] + [a[i]]
max_len = len(max_list)
if max_len > ans_max:
ans_max = max_len
ans_list = max_list
ans.append(max_list)
print(ans_max)
print(*ans_list)
비슷한 문제
11054번. 가장 긴 바이토닉 부분 수열
11055번. 가장 큰 증가하는 부분 수열
11722번. 가장 긴 감소하는 부분 수열
12015번. 가장 긴 증가하는 부분 수열 2
12738번. 가장 긴 증가하는 부분 수열 3
14002번. 가장 긴 증가하는 부분 수열 4
14003번. 가장 긴 증가하는 부분 수열 5
