서론
브루트포스, DP 문제입니다.
17485번 진우의 달 여행 (Large) 문제와 동일한 코드로 풀었습니다.
이 문제의 경우엔 위 문제보다 n과 m의 범위가 훨씬 작아 브루트포스로도 해결할 수 있습니다.
하지만, DP로 푸는게 더 편해서 DP로 해결하였습니다.
난이도
실버 3
문제
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 256 MB |
우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.
[예시]
진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.
- 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.
- 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.
진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.
최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.
입력
첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다.
다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
출력
달 여행에 필요한 최소 연료의 값을 출력한다.
예시
예제 입력 1
6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58예제 출력 1
29
풀이
3차원 배열의 DP를 이용하여 풀었습니다.
dp[0]은 대각선 왼쪽 방향, dp[1]은 아래 방향, dp[2]는 대각선 오른쪽 방향입니다.
같은 방향이 연속으로 진행되면 안되기 때문에,
dp[0]은 이전 값의 dp[1]과 dp[2]만
dp[1]은 이전 값의 dp[0]과 dp[2]만
dp[2]는 이전 값의 dp[0]과 dp[1]만 받을 수 있습니다.
가장 첫 번째 열의 경우, 이전 값에서 오른쪽 아래로 향하는 길이 없기 때문에
대각선 왼쪽 방향은 위쪽에서 아래로 향하는 길만 가능
아래 방향은 대각선 오른쪽에서 왼쪽 아래로 향하는 길만 가능
대각선 오른쪽 방향은 위쪽에서 아래로 향하는 길과 오른쪽 위에서 왼쪽 아래로 향하는 길만 가능합니다.
마지막 열의 경우, 이전 값에서 왼쪽 아래로 향하는 길이 없기 때문에
대각선 왼쪽 방향은 위에서 아래로 향하는 길과 왼쪽 위에서 오른쪽 아래로 향하는 길만 가능
아래 방향은 왼쪽 위에서 오른쪽 아래로 향하는 길만 가능
대각선 오른쪽 방향은 위에서 아래로 향하는 길만 가능합니다.
중간 열이 경우, 이전 값에서 향하는 길을 모두 받을 수 있기 때문에(같은 방향 제외)
대각선 왼쪽 방향은 위에서 아래로 향하는 길과 왼쪽 위에서 오른쪽 아래로 향하는 길만 가능
아래 방향은 왼쪽 위에서 오른쪽 아래로 향하는 길과 오른쪽 위에서 왼쪽 아래로 향하는 길만 가능
대각선 오른쪽 방향은 오른쪽 위에서 왼쪽 아래로 향하는 길과 위에서 아래로 향하는 길만 가능합니다.
각각의 경우 중 더 작은 값을 집어 넣으며 dp배열을 완성시키고, 마지막 행 중에서 가장 작은 값들을 출력하면 됩니다.
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0] * m for _ in range(n)] for _ in range(3)] # 3차원배열 DP
ans = sys.maxsize # 임의의 큰 값
for z in range(3):
for y in range(m):
dp[z][0][y] = board[0][y] # 초기 DP 초기화
for x in range(1, n):
for y in range(m):
if y == 0:
# 가장 첫 번째 열인 경우
# 대각선 왼쪽 방향(dp[0])의 경우, 바로 위에서 아래 방향으로 진행하는 값만 받을 수 있음
# 아래 방향(dp[1])의 경우, 오른쪽 위에서 왼쪽 아래 방향으로 진행하는 값만 받을 수 있음
# 대각선 오른쪽 방향(dp[2])의 경우, 오른쪽 위에서 대각선 왼쪽 진행하는 값과 바로 위에서 아래 방향으로 진행하는 값만 받을 수 있음
dp[0][x][y] = dp[1][x - 1][y]
dp[1][x][y] = dp[0][x - 1][y + 1]
dp[2][x][y] = min(dp[0][x - 1][y + 1], dp[1][x - 1][y])
elif y == m - 1:
# 가장 마지막 열인 경우
# 대각선 왼쪽 방향(dp[0])의 경우, 바로 위에서 아래 방향으로 진행하는 값과 왼쪽 위에서 대각선 오른쪽 방향으로 진행하는 값만 받을 수 있음
# 아래 방향(dp[1])의 경우, 왼쪽 위에서 오른쪽 아래 방향으로 진행하는 값만 받을 수 있음
# 대각선 오른쪽 방향(dp[2])의 경우, 바로 위에서 아래 방향으로 진행하는 값만 받을 수 있음
dp[0][x][y] = min(dp[1][x - 1][y], dp[2][x - 1][y - 1])
dp[1][x][y] = dp[2][x - 1][y - 1]
dp[2][x][y] = dp[1][x - 1][y]
else:
# 중간 열인 경우
# 대각선 왼쪽 방향(dp[0])의 경우, 바로 위에서 아래 방향으로 진행하는 값과 왼쪽 위에서 대각선 오른쪽 방향으로 진행하는 값만 받을 수 있음
# 아래 방향(dp[1])의 경우, 오른쪽 위에서 대각선 왼쪽 방향으로 진행하는 값과 왼쪽 위에서 대각선 오른쪽 방향으로 진행하는 값만 받을 수 있음
# 대각선 오른쪽 방향(dp[2])의 경우, 오른쪽 위에서 대각선 왼쪽 방향으로 진행하는 값과 바로 위에서 아래 방향으로 진행하는 값만 받을 수 있음
dp[0][x][y] = min(dp[1][x - 1][y], dp[2][x - 1][y - 1])
dp[1][x][y] = min(dp[0][x - 1][y + 1], dp[2][x - 1][y - 1])
dp[2][x][y] = min(dp[0][x - 1][y + 1], dp[1][x - 1][y])
for z in range(3): # 원래 자신의 좌표값 더함
dp[z][x][y] += board[x][y]
for z in range(3): # 3차원 배열 중 마지막 행의 최솟값을 찾음
ans = min(ans, min(dp[z][-1]))
print(ans)실행 결과
