문제
개의 돌에는 수 로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.
개의 돌이 일렬로 나열 되어 있다.- 항상 오른쪽으로만 이동가능하다.
- 번째 돌로 이동할 때 × (1 + | |) 만큼 힘을 쓴다. 번째 돌에서
- 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 이다.
이때, 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.
입력
첫 번째 줄에 돌의 개수 와 쓸 수 있는 최대 힘 가 공백으로 구분되어 주어진다.
두 번째 줄에는 개의 돌의 수 가 공백으로 구분되어 주어진다.
출력
가장 오른쪽에 있는 돌로 이동할 수 있다면 YES를 출력한다. 만약 이동하지 못하는 경우에는 NO를 출력한다.
제한
코드
n, k = map(int, input().split())
stone = list(map(int, input().split()))
dp = [False] * n
dp[0] = True
for j in range(1, n):
for i in range(j):
if not dp[i] or dp[j]: # i번째 돌이 올 수 없는 돌이거나 j번째가 이미 올 수 있음이 확인된 경우
continue
energy = (j-i) * (1+abs(stone[i]-stone[j]))
if energy > k: # 쓸 수 있는 최대 힘보다 힘이 더 필요해서 못 감
continue
dp[j] = True
print("YES" if dp[n-1] else "NO")
dp 배열에 i번째 돌에 올 수 있는지 여부를 저장한다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 9084번 동전 (0) | 2023.04.12 |
---|---|
[Python/파이썬] 백준 15486번 퇴사 2 (0) | 2023.04.11 |
[Python/파이썬] 백준 21317번 징검다리 건너기 (0) | 2023.04.11 |
[Python/파이썬] 백준 10844번 쉬운 계단 수 (0) | 2023.04.10 |
[Python/파이썬] 백준 9465번 스티커 (0) | 2023.04.10 |