백준_가장 긴 증가하는 수열 세트 (1)

문제

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12738

12738번: 가장 긴 증가하는 부분 수열 3

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

풀이

1) 가장 긴 증가하는 수열 1

[10, 60, 20, 10, 30, 20, 50] 이 주어졌다고 할 떄 아래처럼 표현할 수 있다.

index	item	증가하는 수열	수열의 길이
0	10	10	1
1	60	10, 60	2
2	20	10, 20	2
3	10	10	1
4	30	10, 20, 30	3
5	20	10, 20	2
6	50	10, 20, 30, 50	4

4번째 증가하는 수열의 길이를 구한다고 하자.

1. 0~3번째 중 item이 30보다 작은 경우를 확인한다. 

2. 그 중 가장 긴 수열의 끝에 30을 덧붙인다.

수열의 길이를 1차원 리스트(dp)에 저장해두고, 반복 연산한다.

2) 가장 긴 증가하는 수열 4

가장 긴 증가하는 수열1을 응용한다. dp에 적혀있는 수열의 길이를 이용한다. 위의 예시를 사용하면, 아래와 같은 dp를 얻을 수 있다.

dp = [1, 2, 2, 1, 3, 2, 4]

가장 오른쪽 원소부터 거꾸로 접근하면서, 수열의 원소들을 찾아 넣는다.

1. 4를 찾는다. → index = 6, item = 50

2. 3을 찾는다. → index = 4, item = 30

3. 2을 찾는다. → index = 2, item = 20

4. 1을 찾는다. → index = 0, item = 10

 

거꾸로 출력해준다. → 50 30 20 10

코드

1) 가장 긴 증가하는 수열 1

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = list(map(int, input().strip().split()))
dp = [1, ]*N

# 오른쪽으로 가면서 찾기
for now in range(N) :
    # 왼쪽에서 작은 값 찾기
    for prev in range(now) : 
        if arr[prev]<arr[now] : 
            dp[now] = max(dp[now], dp[prev]+1)

count = max(dp) # 가장 긴 배열의 길이
print(count)

2) 가장 긴 증가하는 수열 4

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = list(map(int, input().strip().split()))
dp = [1, ]*N

# 오른쪽으로 가면서 찾기
for now in range(N) :
    # 왼쪽에서 작은 값 찾기
    for prev in range(now) : 
        if arr[prev]<arr[now] : 
            dp[now] = max(dp[now], dp[prev]+1)

count = max(dp) # 가장 긴 배열의 길이
print(count)

# 추적해서 배열 찾기
answer = list()
for i in range(N-1, -1, -1) :
    if dp[i] == count : 
        answer.append(arr[i])
        count -= 1

# 출력하기
for it in answer[::-1] : print(it, end = " ")