[Python][DP] 징검다리 - Softeer 3단계

[문제]

출처 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=390

 

[알고리즘] 

• DP 문제이다. 
• 징검다리 하나씩 다음을 반복한다. (i 번째)
  • 이전까지의 모든 징검다리와 다음을 비교한다.(j 번째) 
    • i번째 징검다리가 j 번째 징검다리보다 높이가 크다면, i번째에 저장된 최대개수와 j번째 저장된 최대개수 + 1 의 최대값을 i번째 최대개수로 저장한다. 

 

[느낀점 / 깨달은 점]

• DP 문제가 아직은 완전히 친숙치는 않은것 같다.

 

[코드]

import sys
from collections import deque

N = int(input())

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

dp = [1] * N 

for i in range(1, N):
    for j in range(i):
        if a[i] > a[j] : 
            dp[i] = max(dp[i] , dp[j]+1)

print(max(dp))​