[백준] 11053 가장 긴 증가하는 부분 수열

Hyun·2024년 3월 7일

DP 백준

백준

목록 보기

32/92

문제

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

예제 입력

6
10 20 10 30 20 50

예제 출력

풀이

가장 앞에 있는 숫자부터 해당 숫자가 가질 수 있는 수열의 최대 길이를 구한다. 그러나 모든 숫자는 중복될 수 있기 때문에 값에 대해 최대 길이를 저장하는 게 아니라, 인덱스에 대해 최대 길이를 저장한다.

i번째 수열의 최대 길이를 구하는 방법은 다음과 같다(i >= 1 기준)
1. 1~i-1번째 값을 순회한다(인덱스 j라 가정)
2. arr[j] < arr[i] 이면서 dp[j]가 가장 큰 값을 찾는다
3. dp[i] = dp[j] + 1 을 해준다

우리가 찾는건 i번째이므로 이중 for문을 사용하여 모든 번째에 대해 동일한 과정을 거친다.

풀이

n = int(input())
arr = list(map(int,input().split()))
dp = [0]* n
dp[0] = arr[0]

for i in range(n):
    mx = 0
    for j in range(0, i):
        if arr[j] < arr[i] and dp[j] > mx:
            mx = dp[j]
    dp[i] = mx + 1
print(max(dp))

다시 풀기

1
처음에 dp 를 생각해서 dp 의 기록 방식을 dic 로 택하고, dp 를 구할 때 나보다 작으면서 가장 많은 수열의 개수를 가진 값을 찾기 위해 딕셔너리를 순회하는 것을 택했었다.

그러나, 딕셔너리는 순서를 보장하지 않기 때문에 딕셔너리에 저장된 key 값들의 순서가 arr 배열의 값들의 순서와 일치하지 않는다. 그러므로 이렇게 하면 안된다.

dp 의 순서를 딕셔너리에 기록하는게 아니라!, dp 의 값만을 dic 에 기록하는게 올바른 선택이다. 따라서 딕셔너리를 사용할 때 순서를 고려하는 것은 잘못된 방향이다.

잘못된 풀이 1

import sys
input = sys.stdin.readline
dic = {}

for v in arr:
    max_key = 0
    for k in sorted(list(dic.keys())):
        if k < v and  max_key < k:
            max_key = k
    
    if max_key == 0:
        dic[v] = 1
    else:
        dic[v] = dic[max_key] + 1

print(max(dic.values()))

그래서 아래와 같이 딕셔너리에는 값을 기록하는 용도로만 사용하였다. 여기서는 따로 dp 배열을 생성하지 않았다. dp 없이 arr 배열을 사용하여 문제를 풀었다.

여기서 핵심은 arr 의 현재 위치 이전까지의 값들 중 가장 큰 값을 고르는게 아니라, 해당 값을 마지막으로 하는 수열 중 가장 긴 수열을 가지는 값을 찾는 것이다.

딕셔너리[val]: val 값을 마지막으로하는 가능한 수열 중 가장 긴 수열의 값의 개수

DP 배열 없이 값 기록을 위한 딕셔너리 사용

n = int(input().strip())
arr = list(map(int,input().split()))
dic = {}

for i in range(0, len(arr)) :
    max_v = 0
    # arr 을 돌면서 나보다 작은 수 중에 
    # 가장 긴 수열을 가지는 값을 구함
    for j in range(0, j):
        if arr[j] < arr[i] and max_v < dic[arr[j]]:
            max_v = dic[arr[j]]

    dic[i] = max_v + 1

print(max(dic.values()))

위에서 dp 배열 없이 입력 배열(arr)과, 값 기록을 위한 딕셔너리를 사용했다면, 아래와 같이 dp 배열을 사용해서 풀 수도 있다. 이 경우에는 arr 배열의 인덱스로 dp 배열에 값을 기록하고 접근하였다.

DP 배열 사용

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

for i in range(0,len(arr)):
    mx = 0
    for j in range(0, i):
    	# arr 을 돌면서 나보다 작은 수 중에 
    	# 가장 긴 수열(dp의 값이 길이임)을 가지는 값을 구함
        if arr[j] < arr[i] and dp[j] > mx:
            mx = dp[j]

    dp[i] = mx + 1

print(max(dp))