baekjoon
[백준/BOJ] 11052번 가장 긴 증가하는 부분 (Python)
riley_dev
2021. 2. 25. 17:05
[백준/BOJ] 11052번 가장 긴 증가하는 부분
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
이 문제는 처음에 문제를 애매하게 이해해서, 정확하게 이해하기 위해 검색을 했다. 덕분에 이 문제가 다이나믹 프로그래밍의 문제중에 대표적인 문제라는걸 알았다. 방향을 잡고 문제를 푸니 생각보다 금방 풀었다. 규칙이 잘 보이는 dp문제는 이제 살짝 감을 잡은 것 같다.
Python code
더보기
n=int(input())
a=list(map(int, input().split()))
dp=[0]*n
max_value=0
for i in range(n):
for j in range(i):
if a[i]>a[j]:
dp[i]=max(dp[i],dp[j])
dp[i]+=1
max_value=max(dp[i],max_value)
print(max_value)