[백준] 14863 서울에서 경산까지

문제

• 서울에서 시작해 N개의 도시를 특정 순서로 방문한 뒤 경산에 도착하려고 한다.
• 각 도시를 도보와 자전거로 이동하는데 걸리는 시간과 모금액이 주어질 때, 제한 시간 내에 모금할 수 있는 최대 금액 구하기

 

• 3 <= N <= 100
  0 <= K <= 100,000

 

풀이 1

• 방문해야할 순서대로 가능한 경로를 모두 찾아주면 된다.
• 처음엔 그리디하게 방문하는 걸로 풀었는데, 이렇게 되면 최대 2^N 개의 경우의 수가 생기기 때문에 문제가 있는 것 같다.

29점..

N, K = map(int, input().split())
# 도보 시간, 도보 모금액, 저전거 시간, 자전거 모금액
inform = [0]+[list(map(int, input().split())) for _ in range(N)] 

# routes : n번째 도시까지 k시간 내에 여행할 때 최대 모금액
routes = set()
routes.add((inform[1][1], inform[1][0]))
routes.add((inform[1][3], inform[1][2]))

for end in range(2, N+1) :
    wt, wm, bt, bm = inform[end]
    # 이전 도시까지의 기록에서 도보와 자전거 이동 추가
    new_routes = set()
    for (money, time) in routes :
        if time + wt <= K :
            new_routes.add((money+wm, time+wt))
        if time + bt <= K :
            new_routes.add((money+bm, time+bt))
    routes = new_routes

print(sorted(list(routes))[-1][0])

 

 

풀이 2

• 이전 기록 + 현재 값을 모두 기록하지 않고, 도보와 자전거로 가는 두 가지 길의 최댓값만 기록하도록 변경했다.

여전히 29점...
-> knapsack 방법으로 푼 풀이가 있던데 참고해서 다시 풀어보자

from collections import defaultdict

N, K = map(int, input().split())
# 도보 시간, 도보 모금액, 저전거 시간, 자전거 모금액
inform = [list(map(int, input().split())) for _ in range(N)] 

# dp[n][k] : n번째 도시를 k시간에 도착했을 때 최대 모금액
dp = [defaultdict(int) for _ in range(N)]
dp[0][inform[0][0]] = inform[0][1] if inform[0][0] <= K else 0
dp[0][inform[0][2]] = inform[0][3] if inform[0][2] <= K else 0

for i in range(1, N) :
    for k in dp[i-1] :
    	# 도보
        if k + inform[i][0] <= K :
            dp[i][k+inform[i][0]] = max(dp[i][k+inform[i][0]], dp[i-1][k]+inform[i][1])
        # 자전거
        if k + inform[i][2] <= K :
            dp[i][k+inform[i][2]] = max(dp[i][k+inform[i][2]], dp[i-1][k]+inform[i][3])
        
print(max(dp[N-1].values()))

 

 

References

• 백준 오늘의 문제