[알고리즘/동적 계획법] 21317번 : 징검다리 건너기 - python

링크 : https://www.acmicpc.net/problem/21317

21317번: 징검다리 건너기

 

---

• 문제
• 소요시간 : 45분 실패(코드 수정 필요)

 

---

• 설계하기(접근방법) 

1. n과, 각각의 에너지를 입력받는다

 

2. 알고리즘 해석

 

시작위치 : 돌 1

 

종료 위치: 돌 n

 

점프의 종류

1) 작은 점프 + 1

2) 큰 점프 + 2

3) 아주 큰 점프 + 3

 

식을 풀어보면

dp[2] = jump[1][0]

dp[3] = min(dp[2] + jump[2][0], jump[1][1])

dp[4] = min(dp[3] + jump[3][0], dp[2] + jump[2][1], dp[1] + gj)

 

이런 식으로 진행될 것이다.

기본 식은 

dp[i] = min(dp[i - 1] + jump[i - 1][0], dp[i - 2] + jump[i - 2][1]) 로 진행될 것이지만

매우 큰 점프가 이 식의 일반성을 해친다

 

따라서 모든 dp를 구한 후에

dp[i]- dp[i-3]의 최대값이 바로 아주 큰 점프를 써야하는 순간일 것이다

ex) gj(아주 큰 점프) = 4이고

dp[1] = 0

dp[2] = 3

dp[3] = 5

dp[4] = 10

dp[5] = 14

dp[6] = 24 일때

 

dp[4] - dp[1] = 10

dp[5] - dp[2] = 11

dp[6] - dp[3] = 19 이다

즉 dp[3]에서 dp[6]으로 gj를 쓰는 것이 가장 효율적이다

 

따라서 dp[6]의 값을 dp[3] + gj로 변경한 후 식을 재 순회한다.

 

3. dp[n]의 값을 출력한다

 

 

 

 

---

• 코드(출력)

n = int(input())

dp = [0 for _ in range(n+1)]
jump = [[0, 0]]
energy_max = 0

for i in range(n - 1):
    e = list(map(int, input().split()))  # 1 2, 2 3, 4 5
    jump.append(e)

gj = int(input())


for i in range(2, n + 1):
    if i == 2:
        dp[i] = jump[1][0]
    else:
        dp[i] = min(dp[i - 1] + jump[i - 1][0], dp[i - 2] +
                    jump[i - 2][1])  # 먼저 작은 점프 큰 점프로만 dp를 구한다


for i in range(4, n + 1):
    energy = dp[i] - dp[i - 3]
    if energy > energy_max:
        energy_max = energy
        flag = i

print(energy_max, 'energy max', gj, 'gj0')

if energy_max > gj:
    dp[flag] = dp[flag - 3] + gj
    for i in range(flag + 1, n + 1):
        if i == flag + 1:
            dp[i] = dp[flag] + jump[i-1][0]
        else:
            dp[i] = min(dp[i - 1] + jump[i - 1][0], dp[i - 2] +
                        jump[i - 2][1])

print(dp[n])

---

• 얻어갈 부분

1. 처음 순회할 때 원하는 값을 얻지 못할 때에는, 조건 하나를 뺀 후 재순회해서 추가하는 방법도 있다