CodeDrive

문제:

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다

예를 들어 여행 루트가 다음과 같고 K=1,650 일 때,

1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

풀이방법:

동적계획법을 사용해서 풀어야 하는 문제이다. 0번째 인덱스에는 도보로 걸리는 시간, 2번째 인덱스에는 자전거 이동시 걸리는 시간이 담겨 있으며. 1번째, 3번째 인덱스에는 각각 금액이 담겨져 있다. 따라서 0,2번째로 K시간이 넘어가지 않는 선에서 1,3을 더 했을 때 최대가 되는 값을 찾으면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42899