K. Travel Card

버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다.

문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다.

D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용

위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다.

위 처럼 정의했을 때, 점화식은 직관적이게 생각 가능하며 시간복잡도는 $O(ND)$가 된다. 여기서 $D$는 정기권의 최대 기간이며 문제에서 $D \leq 30$이다.

#include <stdio.h> #include <algorithm> using namespace std; #define MAXN 10004 typedef long long lld; int T, N; lld B[MAXN], R[MAXN], D[MAXN][31]; int main() { int i, j, k; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i<=N;i++){ int a,b; scanf("%d%d", &a, &b); B[i] = B[i-1]+a, R[i] = R[i-1]+b; } for (i=0;i<=N;i++) for (j=0;j<31;j++) D[i][j] = 1e16; D[0][0] = 0; for (i=0;i<N;i++){ D[i+1][0] = min(D[i+1][0], D[i][0] + min(min((B[i+1]-B[i])+(R[i+1]-R[i])*2, 3+(R[i+1]-R[i])*2), 6LL)); D[i+1][7] = min(D[i+1][7], D[i][0] + 18); D[i+1][30] = min(D[i+1][30], D[i][0] + 45); for (j=0;j<31;j++) if (D[i][j] < 1e16){ if (j) D[i+1][j-1] = min(D[i+1][j-1], D[i][j] + min((R[i+1]-R[i])*2, 6LL)); k = max(j-7, 0); if (i+7 <= N) D[i+7][k] = min(D[i+7][k], D[i][j] + 36); k = max(j-30, 0); if (i+30 <= N) D[i+30][k] = min(D[i+30][k], D[i][j] + 90); } } lld ans = 1e16; for (i=0;i<31;i++) ans = min(ans, D[N][i]); printf("%lld\n", ans); } }