softeer - 파이썬 level3 징검다리

🫠 문제

 

🫠 풀이 방법

전형적인 dp 문제입니다. 하지만 dp에 익숙하지 않은 저는 처음에 dp 문제인지 파악이 힘들었습니다ㅎㅎ

dp문제도 열심히 연습해야겠습니다 😭

사실 답안을 봤음에도 처음에는 이해하기 어려웠습니다.

 

아래는 제가 이해한 내용입니다.

• 바깥 for문: 우선 돌다리를 처음부터 끝까지 한번 탐색합니다.
  • 안쪽 for문:
  • 탐색할 때, 현재 탐색하는 돌(stones[i])와 지나온 돌(stones[j])값을 비교합니다.
  • 현재 탐색하는 돌(stones[i])이 지나온 돌(stones[j])보다 높다면 건널 수 있다는 뜻입니다!
  • 그래서 지나온 돌을 건널 때(dp[j]+1)와 건너지 않을 때(dp[i])의 값을 비교하여 큰 값을 현재 돌의 dp값으로 업데이트 합니다.
  • 이렇게 해 주면 dp array의 각 값은 각 돌다리까지의 건널 수 있는 돌의 최대 개수가 담기게 됩니다

🫠 문제 풀이

import sys

N = int(sys.stdin.readline())
stones = list(map(int, sys.stdin.readline().split()))
dp = [1]*N

for i in range(1, N):
    for j in range(0, i):
        now = stones[i] # 1~N 
        prev = stones[j]
        if stones[i] > stones[j]: # 만약 이전 돌보다 현재 돌이 높다면
            # 건널 수 있음. dp값 업데이트!
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))