[소프티어] 징검다리

https://softeer.ai/practice/6293/history?questionType=ALGORITHM

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

 

접근

---

• 밟을 수 있는 돌의 최대 개수를 구해야 한다
  → N의 최댓값은 3000으로, O(N**2)의 시간복잡도가 가능하다
  → 인덱스 i에 대해, i-1 까지의 최장 길이를 구한다. '최장 길이 + 1' 이 현재 인덱스에 대한 최장 길이를 의미한다
  

 

최장 증가 수열(LIS, Longest Increasing Subsequence)

---

https://4legs-study.tistory.com/106

최장 증가 수열 (LIS, Longest Increasing Subsequence)

 

코드

---

import sys
input = sys.stdin.readline

n = int(input())
rocks = list(map(int, input().split()))

dp = [1] * n

for i in range(n):
    temp = 0
    for j in range(i):
        if rocks[i] > rocks[j]:
            temp = max(temp, dp[j])
    dp[i] = temp+1

print(max(dp))