본문으로 건너뛰기

21317 - 징검다리 건너기

info

풀이 키워드​

스포주의

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()

풀이 해설​

처음에 로직을 잘못 짜서 이 부분 다시 짚어봄

왜 이 코드는 틀림?​

def dp(i, jmp): # dp: i번째 돌에서 jmp의 점프를 할때의 최소 에너지

    # base case ...
    # memoization ...

    a, b, c = 0, 0, 100000
    a = dp(i+1, 0) + energy[i][0]
    b = dp(i+2, 1) + energy[i][1]
    if k_avail:
        k_avail = False
        c = dp(i+3, 2) + k
        k_avail = True

    # return ...

상단은 WA 받은 코드의 재귀 호출 단이다. a, b는 무지성 호출하고 c만 점프했는지에 따라 지성적으로 판단한다. (해당 플래그는 global 선언)


※ 대충 그린 상태 (상태 공간 트리로 수정해야 할듯)

dp 콜스택1+2

편의를 위해 2단점프와 기본점프만 있다고 가정하자.

그림과 같이 depth 4로는 2단점프 1번 또는 기본점프 3번으로 도달 가능하다.

그럼 이제 depth 4에서 depth 7로 어떤 선택지가 있는지 생각해보자.

플래그를 False 처리하고 2단점프를 호출했기에, 해당 호출을 기점으로 한 자식 콜에서는 2단점프를 하지 못할 것이다.

한편, 착실하게 한칸씩 도달했던 콜에선 여전히 2단점프가 가능할 것이다.

그렇게 depth 4에선 또다시 2가지 방식으로 재귀호출이 일어난다.

그렇다면? return 값 판정도 섞이게 된다.


Why?​

예를 들어 depth 4에서 return된 a, b, c를 평가했더니, 2단점프 결과가 제일 좋았다고 생각해보자.

그럼 c를 선택하고 return 해서 다시 쭉쭉 depth 1로 올라간다. 능지가 있다면 여기선 c를 평가에서 제외해야 함을 잘 알 것이다.

하지만 저 코드에선 고려가 된다. 알고보니 depth 4에서 선택했던 c값은, depth 4 ~ depth 7까지 착실히 갔던 놈이 가져다준 결과였던 것이다.

결론적으로, DP state가 겹쳐있다는 것이 원인이다.


메모​

  • 각각의 dp state를 구분하는데에 k_avail이 유의미한가? 를 생각해보면 안헷갈림
    • 코테 수준에선 웬만하면 인자 2개인듯
    • main에서 초기값 넣기 애매한건 의심해보기