21317 - 징검다리 건너기
info
- 문제 보기: 21317 - 징검다리 건너기
- 소요 시간: 약 40~50분
- 풀이 언어:
python
- 체감 난이도: 3️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
DP
풀이 코드
info
- 메모리: 31120 KB
- 시간: 40 ms
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, k = 0, 0
energy = [None]
memo = []
def dp(i, k_avail):
global memo
if i == n:
return 0
if i > n:
return 100000
if memo[i][k_avail]:
return memo[i][k_avail]
a, b, c = 0, 0, 100000
a = dp(i+1, k_avail) + energy[i][0]
b = dp(i+2, k_avail) + energy[i][1]
if k_avail:
c = dp(i+3, False) + k
mn = min(a, b, c)
memo[i][k_avail] = mn
return mn
def solution():
global n, k, energy, memo
n = int(input())
for _ in range(n-1):
energy.append(list(map(int, input().split())))
memo = [[0 for _ in range(3)] for _ in range(n)]
k = int(input())
print(dp(1, True))
if __name__ == '__main__':
solution()
풀이 해설
처음에 로직을 잘못 짜서 이 부분 다시 짚어봄