Python3,DP
문제
입출력
입출력 예시
주요 포인트
dp 수열은 '가장 긴 감소하는 부분 수열의 길이'를 담는다.
dp 수열을 모두 1로 초기화한다. 혼자만 가능할 때는 길이가 1이 될 것이기 때문이다.
이중 반복문 안에 조건식을 처리한다.
수열 a를 돌면서 자기 이전 값보다 작은지 확인한다.
이전 값이 더 큰 경우 감소하는 부분 수열이다.
- 만약 a[i]가 문제의 조건을 만족한다면, 이전의 최대값인 dp[j]에 1을 더한 값이 dp[i]가 된다.
(앞쪽 인덱스에 더 긴 경우가 있었을 수도 있기 때문에 max로 갱신한다.) - a[i]가 조건을 만족하지 못한다면, dp[i]는 이전의 값 그대로인 dp[i]가 된다.
가장 큰 숫자를 dp에 저장하고 출력한다.
최종 코드
n = int(input())
dp = [1 for i in range(n)]
a = list(map(int, input().split()))
for i in range(n):
for j in range(i):
if a[i] < a[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
피드백
역시 조건문 내부 처리하는 것이 어려웠다. a[i] 값이 a[j]보다 큰 지, 작은 지에 따라 dp[i] 본인이 거나 dp[j](= 이전)+1이 들어 간다.
또 dp 수열이 부분 수열의 길이를 나타내기 때문에 1로 초기화해야 한다는 부분을 놓치지 말자.
참고
I mean