BOJ 10456 - Travel Card

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	743	87	40	14.286%

문제

---

You correctly think that owning a car can cost a lot of money and can be a great trouble due to congestion. The public transportation system of your city is made up of buses and trains. The fare rule is as follows.

1. Each bus ride costs $1, and each train ride costs $2.
2. No free transfer: if you want to transfer between buses/trains, you are supposed to buy a new ticket.
3. A daily bus card costs $3 and gives you limitless bus rides within a day (but you need to pay for train rides).
4. A daily travel card costs $6 and gives you limitless bus and train rides within a day.
5. A 7 days bus card costs $18 and gives you limitless bus rides for seven days (but you need to pay for train rides).
6. A 7 days travel card costs $36 and gives you limitless bus and train rides for seven days.
7. A 30 days bus card costs $45 and gives you limitless bus rides 30 days (but you need to pay for train rides).
8. A 30 days travel card costs $90 and gives you limitless bus and train rides for 30 days.

You thought that the rule was too complicated and you did not know how many times you would ride buses or trains. Instead of buying bus card or travel card, you paid single ride fare each time. Now you think that if you bought travel cards, then you would have spent less money.

For example, suppose your travel log for three days is as follows.

Day	Number of bus rides	Number of train rides
1	1	0
2	5	0
3	0	2

If you do not buy any travel card, you will spend $10 in total as you spend $1 on day 1, $5 on day 2, and $4 on day 3. However, you can spend $1 on day 1, $3 on day 2 by buying a daily bus card, and $4 on day 3. In total, you will spend $8, which is smaller than $10 and optimal.

Given the travel logs of n days, write a program which calculates the minimum amount of fare.

입력

---

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing one integers n (1 ≤ n ≤ 10,000), where n is the number of days. Each of the following n lines contains two integers a and b where a is the number of bus rides and b is that of train rides on that day (0 ≤ a, b ≤ 100,000). There is a single space between two integers in the same line.

출력

---

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the minimum amount of fare.

접근

---

처음 문제를 볼 때는 쉽게 느껴졌는데, 알고보니 까다로운 DP 문제였었다.
N이 30이라 가정하고, 30일짜리 버스표를 사고 중간중간 전체 표를 사야되는 케이스가 있었다.

바로 점화식을 서술하겠다. table[i]를 i번째 index의 최소 금액으로 정의한다.
bus[i]는 i번째 날의 버스 금액, train[i]는 i번째 날의 기차 금액으로 정의한다.
그렇다면 table[i]의 값을 구하는 점화식은,

1. table[i - 1] + bus[i] + train[i]
2. table[i - 1] + 3(버스 하루치) + train[i]
3. table[i - 1] + 6(전체 하루치)
4. table[i - 7] + 18(버스 일주일치) + { 7일간의 기차 최솟값 }
5. table[i - 7] + 36(전체 일주일치)
6. table[i - 30] + 45(버스 한달치) + { 30일간의 기차 최솟값 }
7. table[i - 30] + 90(전체 한달치)

중 최솟값을 가지게 된다. { } 안에 있는 기차의 최솟값만 따로 구해주면 된다.
이는 간단하다. 7일간의 기차 최솟값을 구하기 위해서는
이전 7일동안 1일치 전체 이용권을 살 것이냐 그냥 돈을 주고 탈 것이냐를 정하면 된다.
마찬가지로 30일간의 기차 최솟값을 구하기 위해서는
따로 dp table을 놓고, 1일, 7일 전체 이용권을 사용해서 나올 수 있는 최솟값을 찾는다.

풀이

---

우선 코드를 그대로 점화식으로 옮겼다.
arr[i].second는 기차의 요금이 2원이기에 *2씩 해주었다.
train7 function의 코드는 쉬우니 생략하겠다.

train30 function은 1차원 DP로 풀었는데, tmp 배열을 놓고
tmp[i] = min(tmp[i - 1] + arr[i], tmp[i - 1] + 6, tmp[i - 7] + 36)
이라고 생각하면 간단하다. 각 index를 맞춰주는 연산이 들어갔을뿐이다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int T, N, dp[10030];
pair<int, int> arr[10030];

int train7(int idx)
{
	int tmp[8];
	int first = idx - 7;
	tmp[0] = 0;
	FUP(i, first + 1, first + 7)
	{
		tmp[i - first] = tmp[i - first - 1] + min(arr[i].second, 6);
	}
	return tmp[7];
}

int train30(int idx)
{
	int tmp[31];
	int first = idx - 30;
	tmp[0] = 0;
	FUP(i, first + 1, first + 30)
	{
		tmp[i - first] = tmp[i - first - 1] + min(arr[i].second, 6);
		if (i - first >= 7)
		{
			tmp[i - first] = min(tmp[i - first], tmp[i - first - 7] + 36);
		}
	}
	return tmp[30];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN(T);
	MS(arr, 0);
	while (T--)
	{
		MS(dp, 0);
		CIN(N);
		FUP(i, 30, 29 + N)
		{
			CIN2(arr[i].first, arr[i].second);
			arr[i].second *= 2;
			int bus = arr[i].first, train = arr[i].second;
			dp[i] = min({ 
				dp[i - 1] + bus + train,
				dp[i - 1] + 3 + train,
				dp[i - 1] + 6,
				dp[i - 7] + 18 + train7(i),
				dp[i - 7] + 36,
				dp[i - 30] + 45 + train30(i),
				dp[i - 30] + 90 });
		}
		COUT(dp[N + 29]);
		ENDL;
	}


	return 0;
}