[백준 / BOJ] 17485 진우의 달 여행 (Large)

문제

출처 : www.acmicpc.net/problem/17485

17485번: 진우의 달 여행 (Large)

 

 

진우가 지구에서 출발해서 달에 도착했을때, 필요한 자금을 최소화 하는문제다. 

달에서 지구까지 가는길에 각 칸에 자금이 주어진다.

풀이

N,M이 각각 최대 1000이고, 한 인덱스에서 아래로 갈수있는방향이 3가지 (왼쪽아래 오른쪽아래 중간) 이므로 완전탐색으로 풀려고하면

시간초과가 난다.

 

다이나믹 프로그래밍으로 풀어야 했는데, dp배열을 구현하고 사용하는게 힘들었다.

매 탐색마다 (왼쪽위 오른쪽 중간) 3방향으로 오는 경우의 최솟값들을 dp배열에 저장해주며 푼다.

 

dp배열을 3차원으로 만들었는데,

dp[Y][X][위쪽에서 오는방향] = (Y,X에 도달했을때 연료의 합)

 

이런식으로 저장해줬다.

 

예를들어서 N = 100, M = 100일때, (arr에는 인덱스에 해당하는 자금이 있다.)

(3,3)지점까지 갔을때의 최솟값은 (한 방향으로 두번 연속 움직일수 없으므로)

dp[3][3][왼쪽위] = min(dp[2][2][중간] , dp[2][2][오른쪽위]) + arr[3][3];

dp[3][3][중간위] = min(dp[2][3][왼쪽위], dp[2][3][오른쪽위]) + arr[3][3];

dp[3][3][오른쪽위] = min(dp[2][4][왼쪽위], dp[2][4][중간]) + arr[3][3];

이다.

 

매 탐색마다 왼쪽위, 중간, 오른쪽에서 왔는지 봐주면서 그 경로로 왔을때의 최솟값을 3차원 dp배열에 저장해주면서 푼다.

(X가 1일때와 M일때를 조심해서 풀자. 각각 왼쪽위와 오른쪽위에서 오는경우는 존재할수없다.)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17485%20%EC%A7%84%EC%9A%B0%EC%9D%98%20%EB%8B%AC%20%EC%97%AC%ED%96%89%20(Large)/main.cpp

devxb/JJUNalgo