(백준 알고리즘 문제풀이) 1904번 가장 긴 감소하는 수열

문제

문제 링크

 

문제 접근

• 이 문제는 dp에 대한 개념을 정리하기에 좋은 문제인 듯하다.
• step1: N과 수열 받아온다.
• step2: dp의 list를 모두 1로 초기화한다.
• step3: i번째 수열의 이전 값이 i번째 수열 값보다 크면 dp의 i번째를 dp의 i번째와 이전의 dp보다 큰 값이 있다면 그 값에 +1한 것과 비교하여 높은 것을 dp의 i번째에 넣는다.
• step4: dp리스트에서 가장 높은 값을 출력한다.

코드

import sys

N = int(sys.stdin.readline())
array = list(map(int, sys.stdin.readline().split()))

dp = [1] * N

for i in range(N):
    for j in range(i):
        if array[i] < array[j]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

느낀점

이 문제는 항상 볼때마다 새로운 느낌이다. 이 문제와 비슷한 문제를 풀어본 기억이 있었는데 아직 익숙하지 않아서 이와 비슷한 문제를 많이 풀어봐야겠다. 최대한 익숙해지는 것이 가장 좋은듯하다.