[백준 14863번] 파이썬 - 서울에서 경산까지

백준 14863 - 서울에서 경산까지

시간 제한 2초, 메모리 제한 512MB

# 조건

• 배우 한정올 씨는 이번 여름에 서울에서 경산까지 자선 여행을 하면서 모금 활동을 진행할 계획이다.
• 자선 여행에서 거쳐 가게 될 도시의 개수와 순서는 미리 정해져 있으며, 자선 여행은 서울에서 시작하여 각 도시를 정해진 순서대로 단 한 번씩 방문한 후 경산에서 끝난다.
• 서울을 제외한 도시의 개수를 N 이라 하자.
• 이때 서울에서 두 번째 도시까지 가는 구간을 구간 1, 두 번째 도시부터 세 번째 도시까지 가는 구간을 구간 2와 같이 부르기로 하며, 마지막 목적지인 경산에 도착하는 구간을 구간 N 이라 하자.
  • 즉, 구간의 전체 개수는 N이다.
• 구간 사이의 이동은 도보 혹은 자전거 어느 한 쪽을 이용하게 되는데, 각 구간에는 도보로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원)이 정해져 있다.
  • 예를 들어, 서울과 경산 사이에 2개의 도시가 있는 다음과 같은 경우(N = 3)를 생각해 보자.

• 인접한 도시 사이를 도보로 이동하는지 자전거로 이동하는지에 따라 전체 모금액이나 걸리는 시간에 차이가 생기게 된다.
• 한정올 씨는 전체 모금액을 가능한 많이 얻는 방법을 찾고 싶어 한다.
• 위의 예에서는 시간이 충분하다면 모든 구간을 도보로 이동하는 것이 모금액을 최대로 하는 방법이며, 모금액은 200+370+250 = 820원, 여행에 걸리는 시간은 500+800+700 = 2,000분이다.
• 그러나 한정올 씨는 바쁜 스케줄로 인해 자선 여행을 위해 보낼 수 있는 시간이 K분(K는 자연수)으로 한정되어 있다.
  • 위의 예에서 만약 K = 1,650이라면, 1, 2번 구간은 도보로 이동하고 3번 구간은 자전거로 이동하여 모금액을 660원으로 하는 것이 가장 좋은 방법이며, 이때 걸리는 시간은 1,600분이다.
• 위와 같이 각 구간별로 도보 및 자전거로 이동하는 경우 걸리는 시간과 모금액이 주어질 때, 제한시간 이내로 서울에서 경산까지 여행하면서 모금할 수 있는 최대 금액을 찾는 프로그램을 작성하시오. (제한시간 이내에 여행하는 방법은 항상 존재한다.)

입력

• 표준 입력으로 다음 정보가 주어진다.
• 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000).
• 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원), 자전거로 이동할 때 걸리는 시간(분), 이때 얻게 되는 모금액(원)을 나타내는 네 개의 자연수가 차례로 공백으로 분리되어 주어진다.
• 세 번째 줄부터 N+1번째 줄도 마찬가지 형식으로 각 줄마다 네 개의 자연수가 주어지며, 입력은 총 N+1줄로 구성된다.
• 두 번째 줄부터 N+1번째 줄에 주어지는 숫자들 중 시간을 나타내는 숫자(각 줄의 첫 번째, 세 번째 숫자)는 10,000 이하의 자연수, 모금액을 나타내는 숫자(각 줄의 두 번째, 네 번째 숫자)는 1,000,000 이하의 자연수들이다.

출력

• 표준 출력으로 K분 이내로 여행하면서 모금할 수 있는 최대 금액을 출력한다. (K분 이내에 여행하는 방법은 항상 존재한다.)

# 접근 방법

• 최대 100개의 도시를 거치며 자전거와 도보로 이동하는 경우의 수를 탐색해야 하기에, 일반적인 그래프 탐색으로는 서브 테스크만 통과된다.
• 따라서, dp를 이용하여 이전의 결과 값을 재활용해서 답을 구해주어야 한다.
• dp의 전체 크기는 도시의 개수이며, 도시마다 K+1초의 크기를 할당해준다.
• 즉, 각 도시마다 해당 시간으로 들어온 값을 갱신해주면 되는 것이다.
• 이 때, 매 분마다 더한 값이 K보다 작은지 검사해주고 작다면 갱신해준다.
• 2차원 리스트로 풀어주었지만, 딕셔너리 또는 K에서 값을 빼주며 재귀로 푸는 다른 사람들의 풀이가 더 효율적이었다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
info = [[*map(int, input().split())] for _ in range(N)]  
result = 0  
dp = [[0] * (K+1) for _ in range(N)]  
t = info[0]  
dp[0][t[0]] = t[1]  
dp[0][t[2]] = max(dp[0][t[2]], t[3])  
for i in range(1, N):  
    road = [info[i][0], info[i][1]]  
    bike = [info[i][2], info[i][3]]  
    min_time = min(road[0], bike[0])  
    for j in range(K+1):  
        if j + min_time > K:  
            break  
        if dp[i-1][j]:  
            temp_rt = j + road[0]  
            temp_rf = dp[i-1][j] + road[1]  
            temp_bt = j + bike[0]  
            temp_bf = dp[i-1][j] + bike[1]  
            if temp_rt <= K:  
                dp[i][temp_rt] = max(dp[i][temp_rt], temp_rf)  
            if temp_bt <= K:  
                dp[i][temp_bt] = max(dp[i][temp_bt], temp_bf)  
print(max(dp[-1]))