[Python] 소프티어 : 징검다리

https://softeer.ai/practice/info.do?idx=1&eid=390 

Softeer

---

💡 문제 풀이

기본적인 DP 문제이다.

이번 DP 리스트에서는 i번째 징검다리까지의 최댓값을 넣어주면 된다.

따라서, 이번 징검다리를 건널 때 현재 값과 이전 값에서 1 추가한 값과 비교해 주면 된다.

✔️ 느낀 점

기본적인 DP 문제이다! 문제 설명이 딱히 친절하지 않아서 어떻게 할까 고민하다가 쓱 풀었는데 맞았다.

💻 코드

import sys ; input = sys.stdin.readline

n = int(input())
stones = list(map(int, input().split()))
DP = [1] * n

for i in range(1, n):
    for j in range(i):
        if stones[i] > stones[j]:
            DP[i] = max(DP[i], DP[j]+1)

print(max(DP))