[Softeer 연습문제] Lv3. 징검다리 (python)

[Softeer 연습문제] Lv3. 징검다리

 

문제확인 : https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

🔍 풀이

- 단순하게 생각했지만... DP를 이용해 푸는 문제였다!

 

💡 정답코드

import sys

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

dp = [1] * N

for i in range(N):  # i번째 돌을 마지막 돌로 생각
    for j in range(i):  # i보다 앞쪽(j번째)의 돌들과 비교
        if rocks[j] < rocks[i]:  # 증가하는 경우
            dp[i] = max(dp[i], dp[j] + 1) # 가장 많이 돌을 밟는 경우의 수를 구함

print(max(dp))