[백준 22869번] 징검다리 건너기(small)(파이썬)

https://www.acmicpc.net/problem/22869

22869번: 징검다리 건너기 (small)

이 문제같은 경우에는

DFS를 활용해서

맨 오른쪽까지 가는 케이스를 구할 수도 있지만

저는 그렇게 구했더니

시간초과 이슈가 떠서

DP로 구현했습니다.

(문제 알고리즘 분류가 DP이기도 하고....)

dp테이블을 -1로 초기화하고

처음 돌맹이 위치는 1로 넣어줍니다.

그 다음, 1 다음(2부터 N번째 돌까지)

건너갈 수 있는지 여부를 확인하고

건너갈 수 있다면 1을 집어 넣어줍니다.

그리고 다음 돌에서 건너가는 경우를 보는데

여기서 중요한 건

dp가 1인 칸만 건너는 경우를 체크하는 것입니다.

dp칸이 -1이라면

'건너갈 수 없는 칸'이기 때문에

그 칸에서 어디를 갈 수 있다한달

애당초 가지 못하는 칸이기 때문에

굳이 구할 필요가 없죠,

 

#백준 22869번 징검다리

N,K=map(int,input().split())

data=list(map(int,input().split()))

rock=[0]+data

dp=[-1]*(N+1)
dp[1]=1

for i in range(1,N+1):
  if dp[i]==-1:
    continue
  for j in range(i+1,N+1):
    now=(j-i)*(1+abs(rock[i]-rock[j]))
    if now<=K:
      dp[j]=1

  if dp[N]==1:
    print("YES")
    exit()


print("NO")

 

https://intrepidgeeks.com/tutorial/python-bai-jun-22869-small-bridge-crossing-bfsdp

[Python] 백준 22869 징검다리 건너기 small (BFS/DP)

여기서는 BFS를 사용한 풀이도 있으니

참고하시면 좋을 것 같습니다.