[프로그래머스]서울에서 경산까지 #dp

제한시간 내에 최대의 모금액으로 이동할 수 있는 방법?

 

​1. 풀이

(1) dp의 의미

행은 구간, 열은 시간이 되어서 dp[1][1]부터 시작.

dp[i][j]의 의미는 i구간안에서 j시간까지 최대 모금액

(2) 점화식

dp[i][j]=max(dp[i-1][j- (i구간에서 도보이동 시간)]+ i 구간에서 도보이동으로 받는 기부금 ,

dp[i-1][j- (i구간에서 자전거 이동시간)] + i 구간에서 자전거이동으로 받는 기부금)

(3) 유의사항

1. [j - (i구간에서 도보이동 시간)]이 음수가 나오면 안된다. 이러면 시작도 전에 출발한게 된다.

2. 2구간이 이상일때부터 dp[i-1][j- (i구간에서 이동시간)] ==0 이되면 안된다. 이는 아직 이전구간에서 이동을 완료하지 않은 상태이기 때문이다.

 

​2. 소스코드

def solution(K, travel):
    size=len(travel)
    dp=[[0 for i in range(K+1)] for j in range(size+1)]
    
    for i in range(1,size+1):
        for j in range(1,K+1):
            if i==1:
                if j-travel[i-1][0]<0:
                    walk=0
                else:
                    walk=dp[i-1][j-travel[i-1][0]]+travel[i-1][1]
                
                if j-travel[i-1][2]<0:
                    bike=0
                else:
                    bike=dp[i-1][j-travel[i-1][2]]+travel[i-1][3]
                    
                dp[i][j]=max(walk,bike)
                
            else:
                if j-travel[i-1][0]<0 or dp[i-1][j-travel[i-1][0]]==0:
                    walk=0
                else:
                    walk=dp[i-1][j-travel[i-1][0]]+travel[i-1][1]
                    
                if j-travel[i-1][2]<0 or dp[i-1][j-travel[i-1][2]]==0:
                    bike=0
                else:
                    bike=dp[i-1][j-travel[i-1][2]]+travel[i-1][3]
                    
                dp[i][j]=max(walk,bike)
            
    return dp[size][K]