sm 기술 블로그
136. 11053(가장 긴 증가하는 부분 수열) 본문
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int,input().split()))
arrDp = [1 for i in range(N)]
for i in range(N):
for j in range(i):
if arr[i] > arr[j]:
arrDp[i] = max(arrDp[i], arrDp[j]+1)
print(max(arrDp))
문제요약
증가하는 수열이 가장 긴 부분은?
설명
코드는 크게 어렵지 않을 것이다.
7
1 4 5 2 3 4 5
로 보자.
값을 하나하나 다 비교해서 수열이 가장 긴 부분에 대해서 가져가면 된다.
먼저 각 인덱스는 1의 수열을 가질 수 있어 1로 초기화 해주었다.
for i in range(N):
for j in range(i):
if arr[i] > arr[j]:
arrDp[i] = max(arrDp[i], arrDp[j]+1)
arr를 0부터 해당 인덱스(i) 전까지 비교한다.
만약 해당 인덱스가(i) 가 비교 도중 부분 인덱스(j) 보다 크다면 Dp에 저장된 길이를 비교하는데, 자기자신이 가지고 있ㄴ는 길이, 부분 인덱스(j)에서 +1한 길이 중 더 큰 것을 저장한다.
print(max(arrDp))
마지막에 가장 큰 부분을 출력해주면 답을 맞출 수 있다.
'문제 > 백준_파이썬' 카테고리의 다른 글
138. 2565(전깃줄) (0) | 2022.07.10 |
---|---|
137. 11054(가장 긴 바이토닉 부분 수열) (0) | 2022.07.10 |
135. 2156(포도주 시식) (0) | 2022.07.08 |
133. 1463(1로 만들기) (0) | 2022.07.04 |
132. 2579(계단 오르기) (0) | 2022.07.04 |
Comments