백준 11053(가장 긴 증가하는 부분 수열) - python
2023. 10. 8. 23:00ㆍ알고리즘(python)/DP
접근
1. dp를 이용하여 dp[i]를 길이가 i일때 i번째 수로 만들 수 있는 증가하는 부분 수열의 길이로 둔다. dp[i+1]를 구하기 위해 i+1보다 더 작은 수들을 찾는다. 이 수들 중 dp의 값이 가장 큰 수를 j라고 한다면 dp[j]+1 이 dp[i+1] 이 된다.
2. 직접 가장 긴 증가하는 부분 수열을 만든다.
10 12 20 8 9 10 15 30 50 이라는 수열이 있다고 생각해보자.
arr = [0] 를 두고 arr[-1] 보다 크면 추가, 작으면 기존 수와 교체하여 구한다.
arr = [0 10 12 20] 이면 다음 수가 8이다. 이때 기존수 10과 교체한다. 이 문제는 부분 수열의 길이를 구하는 문제이기 때문에 중간에 끝나더라도 길이 자체는 그대로 출력되게 된다.
나의 코드(직접 세기)
import sys
input = sys.stdin.readline
n = int(input())
arr=list(map(int,input().split()))
dp = [1] * (n)
for i in range(1,n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
나의코드(수열 만들기)
import sys
input = sys.stdin.readline
n = int(input())
arr=list(map(int,input().split()))
dp = [0]
for i in arr:
if i > dp[-1]:
dp.append(i)
else:
start = 0
end = len(dp)-1
while end-start != 1:
mid = (start+end)//2
if i > dp[mid]:
start = mid
else:
end = mid
dp[end] = i
print(len(dp)-1)
'알고리즘(python) > DP' 카테고리의 다른 글
백준9251(LCS) - python (0) | 2023.10.07 |
---|---|
백준 1932(정수 삼각형) - python (0) | 2023.10.05 |
백준 1149(RGB) - python (1) | 2023.09.26 |