코드 복사/붙여넣기 하는 당신이 아름답습니다.

10251 : 운전 면허 시험

풀이

dp[i][j][k][d] = (i, j)까지 방향을 k번 틀고 d방향에서 왔을 때의 최소 연료량

아 졸리다 자세한 풀이는 다른 블로그를 보는 게 더 좋겠다!

코드

#include <stdio.h>
#include <string.h>

int min(int a, int b) { return a < b ? a : b; }
int n, m, l, g, dp[102][102][102][2], gas[102][102][2];

int main() {
	int T;
	for (scanf("%d", &T); T; T--) {
		scanf("%d %d %d %d", &n, &m, &l, &g);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j < m; j++) {
				scanf("%d", &gas[i][j][0]);
			}
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf("%d", &gas[i][j][1]);
			}
		}

		memset(dp, 0x3f, sizeof(dp));
		dp[1][1][1][0] = dp[1][1][1][1] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				for (int k = 1; k <= 100; k++) {
					int &d0 = dp[i][j][k][0], &d1 = dp[i][j][k][1];
					int g0 = gas[i][j-1][0], g1 = gas[i-1][j][1];
					int r0 = min(dp[i][j-1][k][0], dp[i][j-1][k-1][1]);
					int r1 = min(dp[i-1][j][k][1], dp[i-1][j][k-1][0]);
					d0 = min(d0, r0 + g0);
					d1 = min(d1, r1 + g1);
				}
			}
		}

		int ans = -1;
		for (int k = 100; k; k--) {
			if (dp[n][m][k][0] <= g) ans = k;
			if (dp[n][m][k][1] <= g) ans = k;
		}

		printf("%d\n", ~ans ? (n + m - 2) * l + ans - 1 : -1);
	}

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-01-30 00:51

Read more posts by this author