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

https://www.acmicpc.net/

 

문제풀이

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

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

dp를 활용해서 푸는 문제인 것은 알았지만 어떤식으로 해결해야할지 처음엔 와닿지 않았다. 입력받은 수열을 하나씩 검사하면서 그 때까지 가장 긴 수열을 dp에 저장해야한다는 것은 생각했다. 그 사이에서 수의 비교를 어떤 식으로 해나가야할지 감이 안잡혔지만, 결국엔 그냥 비교를 다 해보는 것으로 깨달았다. 이전에 지나왔던 수에 대해서 하나씩 비교를 하면서 제일 긴 수열 길이로 해주면 됐다. 

 

예시로 나온 A = {10, 20, 10, 30, 20, 50}을 보자

10부터 50까지 차례대로 검사한다.

 

10일때,

앞에 비교할 대상이 없으므로 단순히 1개 수열이 최대다.

 

20일때,

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

1(10에서의 최대 길이)+1(현재 수 카운트) =2

 

10일때,

10과 비교하면 현재 수가 작음

20과 비교하면 현재 수가 작음

단순히 자신의 수만 카운트하여 1이 최대이다.

 

30일때,

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

20과 비교하면 현재 수가 20보다 더 크기 때문에 20에서 셌던 길이 = 2

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

셋 중 제일 큰 값 2+1 = 3

 

20일때,

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

20과 비교하면 현재 수와 같음

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

30과 비교하면 현재 수보다 큼

그 중 제일 큰 값 1+1 = 2

 

50일때,

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

20과 비교하면 현재 수가 20보다 더 크기 때문에 20에서 셌던 길이 = 2

10과 비교하면 현재 수가 10보다 더 크기 때문에 10에서 셌던 길이 = 1

30과 비교하면 현재 수가 30보다 더 크기 때문에 30에서 셌던 길이 = 3

20과 비교하면 현재 수가 20보다 더 크기 때문에 20에서 셌던 길이 = 2

그 중 제일 큰 값 3+1 = 4

 

[1, 2, 1, 3, 2, 4] 중 제일 큰 길이인 4가 정답

 

Python3

import sys
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
dp = [0]*n
for i in range(n):
    for j in range(i):
        if numbers[j] < numbers[i] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

코드에서는 조건문에서 크기 비교뿐만 아니라 dp에 저장된 값도 비교했다. 조건을 늘려 불필요한 코드실행을 줄인셈!

 

 

비슷한 백준 문제 > 11054번: 가장 긴 증가하는 바이토닉 부분수열

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

11054번: 가장 긴 바이토닉 부분 수열

https://miraekwak.tistory.com/90

[BOJ] 11054번: 가장 긴 증가하는 바이토닉 부분수열