[파이썬] 백준 21317 : 징검다리 건너기 (실버1)

[파이썬] 백준 21317 : 징검다리 건너기 (실버1)

 

21317번: 징검다리 건너기

---

문제

---

풀이

0. 방향성 생각

단방향으로 상태가 나누어져있는 DP. 
2차원 DP로 만들거나, DP배열을 두 개 만든다.

dp0에서 슈퍼점프(2칸 건너뛰는 점프)를 하면 dp1로 이동하는 방식으로 풀었다.

 

1. 입력

n = int(input())
info = [[0,0]]
for _ in range(n-1):
    info.append(list(map(int,input().split())))
superjump = int(input())

첫 번째 돌 부터 출발하므로 인덱스를 맞추기 위해서 더미 [0,0]를 info에 넣는다.

info[i번째 돌][j-1 걸음]

2. 함수 정의

def solution(a):
    if a == 1:
        return 0
    elif a == 2:
        return info[1][0]
    elif a == 3:
        return min(info[1][0]+info[2][0],info[1][1])
    else:
        dp0,dp1 = [0]*(a+1),[0]*(a+1)
        
        dp0[2] = info[1][0]
        for dist in range(3,a+1):
            dp0[dist] += min(dp0[dist-1]+info[dist-1][0],
                             dp0[dist-2]+info[dist-2][1])
        dp1[4] = superjump
        for dist in range(5,a+1):
            if dist == 5:
                dp1[dist] += min(dp1[dist-1]+info[dist-1][0],
                                    dp0[dist-3]+superjump)
            else:
                dp1[dist] += min(dp1[dist-1]+info[dist-1][0],
                                    dp1[dist-2]+info[dist-2][1],
                                    dp0[dist-3]+superjump)
        return min(dp0[-1],dp1[-1])
print(solution(n))

a==1 일 때는 그 자리에서 산삼을 캘 수 있다.

a==2 일 때는 한 걸음 건너서 산삼을 캘 수 있다.

a==3 일 때는 1+1,2 중 작은 에너지를 소모하는 경로를 선택한다.

 

그 이상일 때는 슈퍼점프를 쓰지 않고 목적지에 도달하는 dp0을 만든다.

다음 도착지 = min(1칸 전에서 출발, 2칸 전에서 출발)

 

 슈퍼점프를 쓰는 경우에는 dp1이라고 정의한다.

1에서 슈퍼점프를 쓰면 4부터 시작한다.

인덱스가 5일 때 따로 나눠준 이유는 5에서 2칸 전인 3은 슈퍼점프를 써서 도달할 수 없다. 없는 경우이다.

인덱스가 6 이상은 1칸 전, 2칸 전, 3칸 전에서 쓰는 경우 중 에너지 최소인 경로를 선택한다.

---

전체코드

n = int(input())
info = [[0,0]]
for _ in range(n-1):
    info.append(list(map(int,input().split())))
superjump = int(input())

def solution(a):
    if a == 1:
        return 0
    elif a == 2:
        return info[1][0]
    elif a == 3:
        return min(info[1][0]+info[2][0],info[1][1])
    else:
        dp0,dp1 = [0]*(a+1),[0]*(a+1)
        
        dp0[2] = info[1][0]
        for dist in range(3,a+1):
            dp0[dist] += min(dp0[dist-1]+info[dist-1][0],
                             dp0[dist-2]+info[dist-2][1])
        dp1[4] = superjump
        for dist in range(5,a+1):
            if dist == 5:
                dp1[dist] += min(dp1[dist-1]+info[dist-1][0],
                                    dp0[dist-3]+superjump)
            else:
                dp1[dist] += min(dp1[dist-1]+info[dist-1][0],
                                    dp1[dist-2]+info[dist-2][1],
                                    dp0[dist-3]+superjump)
        return min(dp0[-1],dp1[-1])
print(solution(n))

코멘트

코드 짧게하려다 틀림... 길어져도 답부터 맞추기.