728x90
반응형
Siver II
# 11053 가장 긴 증가하는 부분 수열
링크 : https://www.acmicpc.net/problem/11053
풀이
N = int(input())
A = list(map(int, input().split()))
dp = [1] * N
for i in range(N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[j]+1, dp[i]) # 이해되지 않는 부분..
print(max(dp))
# 연습 예제
# A = [2,11,4,55,7,9,13,3] → 5
# A = [6,2,5,1,7,4,8,3] → 4
# A = [1,2,8,2,4,8] → 4
후기
- LIS (Longest Increasing Subsequence)에 대한 이해가 필요하다. DP 알고리즘을 통해 이번 문제를 풀 수 있다.
cf. 이분 탐색을 이용해서도 풀 수 있다고 한다. - 사실 꽤 오랫동안 문제풀이에 시간을 쏟았는데 해답을 봐도 100% 이해되지 않는다.
간단하게 풀이과정을 적어보고 넘기자.
다시 공부해서 풀이과정에 확신이 있을 때 정리해서 올려보도록 하겠다. - LIS를 손으로 풀어가는 과정은 자세하게 설명된 영상이 있으니 참고해 볼 것
https://youtu.be/CE2b_-XfVDk
'Algorithm Study > Python' 카테고리의 다른 글
[백준 파이썬] # 2839 설탕 배달 (0) | 2022.02.17 |
---|---|
[백준 파이썬] # 1463 1로 만들기 (0) | 2022.02.17 |
[백준 파이썬] # 2292 벌집 (0) | 2022.02.15 |
[백준 파이썬] # 4153 직각삼각형 (0) | 2022.02.15 |
[백준 파이썬] # 5622 다이얼 (0) | 2022.02.15 |