[BOJ] 10251번: Driving License

https://www.acmicpc.net/problem/10251

시작점에서 도착점까지 도달하는 경로 중에서 최소 방향전환을 해야하는지를 구해야합니다. 만약 연료를 고려하지 않는다면 최소 방향전환은 1번이겠지만 연료 때문에 복잡해집니다. 전수조사를 하게 되면 시간복잡도는 최대 O(200 combination 100) 이 되어 사실상 불가능합니다. 대신 4차원 Dynamic table을 생각합니다

D[i][j][t][d]. t : 턴 횟수 d : 0 - from right, 1 - from upward, 즉 (i, j)에 t번 턴을 해서 도달할 때 필요한 최소 연료량(단 d=0이면 왼쪽에서 온 경우, d=1이면 오른쪽에서 온 경우)

D[i][j][t][0] = D[i][j-1][t][0] < D[i][j-1][t-1][1] ? D[i][j-1][t][0]+row[i][j] : D[i][j-1][t-1][1]+row[i][j];  

D[i][j][t][1] = D[i-1][j][t-1][0] < D[i-1][j][t][1] ? D[i-1][j][t-1][0]+col[i][j] : D[i-1][j][t][1]+col[i][j];

이기 때문에 이 다이나믹 테이블을 전부 채운 이후 D[M-1][N-1][t][0] 혹은 D[M-1][N-1][t][1]이 G 이하가 되는 최소의 t를 찾아 답을 출력하면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/10251.cpp