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

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

---

예제 입력 1

6
10 20 10 30 20 50

---

예제 출력 1

4
10 20 30 50

---

풀이

❓ 어떻게 풀까?

1. dp 리스트 사용

• dp[i]는 i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이를 저장한다.
• 초기에는 각 원소가 하나의 증가 부분 수열을 형성할 수 있으므로, dp 배열을 1로 초기화한다

dp = [1]*n

2. trace 리스트 사용

• trace[i]는 i번째 원소의 바로 이전에 오는 원소의 인덱스를 저장한다.
• 초기에는 각 원소의 이전 원소가 없으므로, trace 배열을 -1로 초기화한다.

trace = [-1]*n

3. dp 리스트 채우기

• 주어진 배열 a의 각 원소에 대해, 그보다 앞에 있는 원소들 중 그 값이 더 작은 원소들을 찾는다.
• 그 중에서 가장 큰 dp 값을 가지는 원소의 dp 값에 1을 더한 값을 현재 원소의 dp 값으로 갱신한다.

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

4. trace 리스트 채우기

• 이때, dp 값을 갱신하는 원소의 인덱스를 trace 배열에 저장한다.
• 이는 나중에 최장 증가 부분 수열을 출력하기 위함이다.

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

5. 가장 큰 dp 값을 가지는 원소의 인덱스를 찾는다.

• 이 원소가 최장 증가 부분 수열의 마지막 원소입니다.

max_idx = dp.index(max(dp))

6. 마지막 원소에서부터 trace 배열을 따라가면서 각 원소를 출력한다.

• 이는 최장 증가 부분 수열을 출력하는 과정이다.

def print_lis(idx):
    if idx == -1:
        return
    print_lis(trace[idx])
    print(a[idx], end=' ')

print(max(dp))
print_lis(max_idx)

---

소스코드

n = int(input())
a = list(map(int, input().split()))

dp = [1]*n
trace = [-1]*n

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

max_idx = dp.index(max(dp))

def print_lis(idx):
    if idx == -1:
        return
    print_lis(trace[idx])
    print(a[idx], end=' ')

print(max(dp))
print_lis(max_idx)