hazxz   7달 전

예전부터 이런 문제를 해결하는 법을 늘 궁금해왔습니다.

어떤 bound를 만족하는 가지들 중 가장 빠른 시간에 갈 수 있는 경로를 찾는 문제인데

점화식을 세울려고 f함수를 만들려고 해도 파라미터로 무었을 줘야 할지...

메모제이션은 기름과 시간, 방향 전부다 해야하는 건지 아닌지 접근하질 못하겠습니다 ㅜㅜ

구글링해봐도 이 문제에 대한 풀이가 나오질 않아서 여기 질문 남깁니다 ㅜㅜ


game2k   7달 전

어떤 경로를 선택하든 직선주행 길이는 같기 때문에 도착점까지 몇번 방향을 바꾸어 도달했는지를 안다면 다음과 같이 답을 구할 수 있습니다.

답 = (M + N - 2 ) * L + 방향을 바꾼 횟수

문제의 예시에서는 3번 방향을 바꾸었기 때문에 (4 + 6 - 2) * 10 + 3 = 83 이 나왔습니다.

따라서 도착점까지 몇 번 방향을 바꾸어 도착하는것이 가장 좋은지를 알아내면 됩니다.


이를 위해 각 지점마다 어느 방향에서 몇 번 방향을 바꿔 도착했을 때 얼마의 연료가 소모되는지를 알고 있으면 됩니다.

1. 위에서 왔는가? 옆에서 왔는가? 를 구분한다.

2. 현재 위치까지 최소 몇번, 최대 몇번 방향을 바꾸어 도달 가능한지 안다.

이상을 고려하면 다음과 같은 4차원 dp배열을 만들 수 있습니다.

dp[i][j][k][dir] = (i, j) 위치에 dir 방향에서 k 번 방향을 바꾸어 왔을때 얻을 수 있는 최소 연료량.

UP = 현재 위치로 오는데 위쪽 방향에서 온 경우

LEFT = 현재 위치로 오는데 왼쪽 방향에서 온 경우 일때

dp[i][j][k][UP] = min(dp[i-1][j][k][UP], dp[i-1][j][k-1][LEFT]) + down[i-1][j]

dp[i][j][k][LEFT] = min (d[[i][j-1][k-1][UP], dp[i][j-1][k][LEFT]) + right[i][j-1]

정도로 점화식을 세울 수 있을 것 같습니다.


댓글을 작성하려면 로그인해야 합니다.