[백준 10456] Travel Card

김동근·2021년 2월 21일
0
post-thumbnail

Travel Card 10456

유형

DP

풀이

혼자힘으로 풀려고 하였지만 실패해서 풀이를 참조하였다. 어려운 dp문제였다고 생각한다.

한번에 여러 티켓을 사용할 수 있고 꼭 7일 30일을 전부 채우지 않아도 티켓을 사용하는게 이득이라면 그렇게하는 것이 최소 비용을 찾을 수 있는 방법이 된다.

dp 테이블은 1차원으로 i일에 필요한 최소 경비로 설정하였다.

dp[i] = min(
	dp[i-1] + 버스요금 + 기차요금,
	dp[i-1] + (버스 1일티켓) + 기차요금
	dp[i-1] + (기차1일티켓),
	dp[i-7] + (버스7일 티켓) + (지난7일간 최소 기차요금),
	dp[i-7] + (기차7일 티켓),
	dp[i-30] + (버스30일 티켓) + (지난30일간 최소 기차요금),
	dp[i-30] + (기차30일 티켓)
)

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n;
pair<int, int> arr[10031];
int dp[10041];

int day7(int s) {
	int temp = 0;
	for (int i = s - 6; i <= s; i++) temp += min(6, arr[i].second);
	return temp;
}

int day30(int s) {
	int DP[31];
	DP[0] = 0;
	for (int i = s - 29, j = 1; i <= s && j <= 30; i++, j++) {
		DP[j] = DP[j - 1] + min(arr[i].second, 6);
		if (j >= 7) {
			DP[j] = min(DP[j], DP[j - 7] + 36);
		}
	}
	return DP[30];
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		memset(dp, 0, sizeof(dp));
		for (int i = 30; i <= n + 29; i++) {
			cin >> arr[i].first >> arr[i].second;
			arr[i].second *= 2;
		}

		for (int i = 30; i <= n + 29; i++) {
			dp[i] = min({
					dp[i - 1] + arr[i].first + arr[i].second,
					dp[i - 1] + 3 + arr[i].second,
					dp[i - 1] + 6,
					dp[i - 7] + 36,
					dp[i - 7] + 18 + day7(i),
					dp[i - 30] + 90,
					dp[i - 30] + 45 + day30(i)
				});
		}

		cout << dp[n + 29] << '\n';
	}
	
	return 0;
}

profile
김동근

0개의 댓글