[Python] 징검다리 (Softeer LEVEL 3)

https://softeer.ai/practice/6293

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

---

문제풀이

DP? 계열의 문제라고 생각된다. 문제 설명이 너무 간단해서 오해가 있었다. "연속된 증가하는 돌"이 아니라 그냥 점점 높이가 높아지기만 하면, 중간 돌들은 띄어 넘을 수 있다.

반복문을 돌면서 현재까지 오면서 밟을 수 있는 최대의 돌 개수를 구하면 된다. 이건 말이 더 어렵다 코드로 한줄이다. 코드를 보자.

코테 보는 회사가 C++이 안되서 파이썬으로 하는데 진짜 간단하긴 한것같다..

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1 for _ in range(n)]

cnt = 0

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

print(max(dp))