[BOJ] 백준 10251번: 운전 면허 시험

운전 면허 시험

문제

(1,1)에서 (M,N)까지 이동하는데 남쪽과 동쪽으로만 이동할 수 있고 위 그림과 같이 이동하는데 길 상태에 따라 연료 g가 소모된다. 방향을 틀 때 1의 시간이 소모되고, 1개 변을 이동할 때 l 시간이 소모될 때 최대 가용 연료 G 이내로 들어올 수 있는 최소 시간을 구하는 문제이다.

문제 풀이

가장 쉽게 떠올릴 수 있는 풀이는 \(O(NMG)\) bfs 서칭 하는 방법이다. 물론 공간, 시간복잡도가 불가능한 풀이이고, 핵심적인 힌트는 이동하는데 걸리는 시간은 이동이 남쪽과 동쪽만 가능하므로 변의 개수는 의미가 없고 방향을 바꾼 횟수만 카운트해주면 된다는 점이다. 따라서 dp 테이블을 \(dp[x][y][k][dir]=(1,1)에서\: (x,y)좌표까지\: k번\: 방향을\: 틀고\: 현재\: dir방향\: 일\: 때\: 최소\: 연료\: 사용량\) 으로 정의한 후 \(dp[M][N][k][dir]\) 테이블에서 k 값과 dir 값을 바꾸면서 dp 값이 G보다 같거나 작은 최소 k 값을 구하면 되는 문제로 바뀌게 된다. dp 테이블 상태가 바뀌는 경우의 수는 남->남, 남->동, 동->남, 동->동 4개이다. 

소스 코드

#include <bits/stdc++.h> using namespace std; int n, m, l, g; int gr[100][100]; int gc[100][100]; int dp[105][105][300][2]; int main(){ int tc; scanf("%d", &tc); while(tc--){ scanf("%d%d%d%d", &n, &m, &l, &g); for(int i=0;i<n;i++) for(int j=0;j<m-1;j++) scanf("%d", &gr[i][j]); for(int i=0;i<n-1;i++) for(int j=0;j<m;j++) scanf("%d", &gc[i][j]); memset(dp, 0x3f, sizeof(dp)); dp[0][0][0][0]=0; dp[0][0][0][1]=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ for(int k=0;k<250;k++){ if(i+1!=n){ dp[i+1][j][k][0]=min(dp[i+1][j][k][0], dp[i][j][k][0]+gc[i][j]); dp[i+1][j][k+1][0]=min(dp[i+1][j][k+1][0], dp[i][j][k][1]+gc[i][j]); } if(j+1!=m){ dp[i][j+1][k][1]=min(dp[i][j+1][k][1], dp[i][j][k][1]+gr[i][j]); dp[i][j+1][k+1][1]=min(dp[i][j+1][k+1][1], dp[i][j][k][0]+gr[i][j]); } } } int ans=0x3f3f3f3f; for(int i=0;i<250;i++){ if(dp[n-1][m-1][i][0]<=g) ans=min(ans, i); if(dp[n-1][m-1][i][1]<=g) ans=min(ans, i); } printf("%d\n", ans==0x3f3f3f3f?-1:(n-1)*l+(m-1)*l+ans); } return 0; }