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

문제 설명

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

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

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

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

제한사항

• travel 배열의 각 행은 순서대로 [도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액]입니다.
• travel 배열 행의 개수는 3 이상 100 이하인 정수입니다.
• travel 배열에서 시간을 나타내는 숫자(각 행의 첫 번째, 세 번째 숫자)는 10,000 이하의 자연수, 모금액을 나타내는 숫자(각 행의 두 번째, 네 번째 숫자)는 1,000,000 이하의 자연수입니다.
• K는 0보다 크고 100,000보다 작거나 같은 자연수입니다.

입출력 예

Ktravelreturn

1650	[[500, 200, 200, 100], [800, 370, 300, 120], [700, 250, 300, 90]]	660
3000	[[1000, 2000, 300, 700], [1100, 1900, 400, 900], [900, 1800, 400, 700], [1200, 2300, 500, 1200]]	5900

입출력 예 설명

입출력 예#1
앞서 설명한 예와 같습니다.

입출력 예#2
1, 4번 구간은 도보로 이동하고 2, 3번 구간은 자전거로 이동하여 모금액을 5,900원으로 하는 것이 가장 좋은 방법입니다. 이때 걸리는 시간은 3,000시간입니다.

---

dp 배열의 인덱스 설정이 까다로웠던 문제이다.

2차원 배열로 설정하고 시간을 인덱스로 해야한다는 점이 까다로웠다.

즉 dp[i][j] = i번째 도시까지 j 시간으로 갔을 때 최대 모금액이다.

따라서 첫번째 도시부터 마지막 도시까지 iteration을 돌면서, 

i-1번째 도시에 몇 시간에 갔는지를 알아내야 한다.

그래서 이중 for문을 사용하고 i-1번째 도시에 방문한 시간을 알아냈으면 그 시간과 i번째 도시에 도보로 갈 때와 자전거로 갈 때 시간을 더해서 K를 초과하는지 조사해야 한다.

K를 초과하지 않는다면 점화식에 맞게 최대 값을 구하면 된다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EC%84%9C%EC%9A%B8%EC%97%90%EC%84%9C%20%EA%B2%BD%EC%82%B0%EA%B9%8C%EC%A7%80.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
int dp[101][100001]; 

int solution(int K, vector<vector<int>> t) {
	int answer = 0;
	dp[0][t[0][0]] = t[0][1];
	dp[0][t[0][2]] = t[0][3];
	for (int i = 1; i < t.size(); i++) {
		for (int j = 0; j <= K; j++) {
			if (dp[i - 1][j] == 0) continue;
			if (j + t[i][0] <= K) {
				dp[i][j + t[i][0]] = max(dp[i][j+t[i][0]],dp[i - 1][j] + t[i][1]);
				answer = max(answer, dp[i][j + t[i][0]]); 
			}
			if (j + t[i][2] <= K) {
				dp[i][j + t[i][2]] = max(dp[i][j+t[i][2]],dp[i - 1][j] + t[i][3]);
				answer = max(answer, dp[i][j + t[i][2]]);
			}
		}
	}
	return answer;
}

int main()
{
	cout << solution(3000, { { 1000,2000,300,700 }, { 1100,1900,400,900 }, { 900,1800,400,700 }, { 1200,2300,500,1200 } });
}