(BOJ) 17484. 진우의 달나라 여행

📗문제 설명

문제 바로가기

💡 우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.

💡 최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요한 연료의 최소값을 계산해 주자.

• 입력
  첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다.
  
• 출력
  달 여행에 필요한 최소 연료의 값을 출력한다.
  

# 예제 입력
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

# 예제 출력
29

💡문제 풀이 IDEA

1. 바닥으로 내려가면서 위에서 min value를 받아서 오자! ( 풀이방법이 그리디로 변형되버림) ->NOT DP. 틀린 접근
2. 3차원으로 값을 받는다.
   1. 1,2차원은 행과 열, 3차원은 각 자리별로 받은 값
   2. 마지막 행에서 제일 작은 값을 출력해준다.

👨🏻‍💻문제 풀이 CODE

from copy import deepcopy

N,M=map(int,input().split()) # N이 행개수, M이 열개수

road=[list(map(int,input().split())) for i in range(N)] # 지도

fuel=[[[601 for k in range(3)] for j in range(M)] for i in range(N)] # 최단 경로 기록
fuel[0]=deepcopy(road[0]) # 출발점은 copy

# 0= left, 1=center, 2=right

for i in range(N-1):
    for j in range(M):
        # 시작점
        if i==0:
            if j==0: # 첫번째 변수일 경우 ( 왼쪽으로 못감)
                fuel[i+1][j][1]=fuel[i][j]+road[i+1][j]
                fuel[i+1][j+1][2]=fuel[i][j]+road[i+1][j+1]
                    

            elif j==(M-1): # 마지막 변수일경우 ( 오른쪽으로 못감 )
                fuel[i+1][j-1][0]=fuel[i][j]+road[i+1][j-1]
                fuel[i+1][j][1]=fuel[i][j]+road[i+1][j]

            else:
                fuel[i+1][j-1][0]=fuel[i][j]+road[i+1][j-1]
                fuel[i+1][j][1]=fuel[i][j]+road[i+1][j]
                fuel[i+1][j+1][2]=fuel[i][j]+road[i+1][j+1]

        # fuel[i][j][0]= left로 받은거 최적의 값, # fuel[i][j][1]= center로 받은거 최적의 값, # fuel[i][j][2]= right로 받은거 최적의 값, 
        else:
            # 시작점이 아닐 경우.
            if j==0: # 첫번째 변수일 경우 ( 왼쪽으로 못감)
                # 가운데로 내려가는 경우 (3번에서 받은걸로 밖에 못감.)
                fuel[i+1][j][1]=fuel[i][j][0]+road[i+1][j]
                 
                # 오른쪽으로 가는 경우. ( 중앙에서 받은거랑 왼쪽에서 받은거 ) 
                fuel[i+1][j+1][2]=min(fuel[i][j][0],fuel[i][j][1])+road[i+1][j+1]
                    
            elif j==(M-1): # 마지막 변수일경우 ( 오른쪽으로 못감 )
                # 왼쪽으로로 내려간다면 ( 중앙에서 온거 )
                fuel[i+1][j-1][0]=min(fuel[i][j][2],fuel[i][j][1])+road[i+1][j-1]

                # 중앙으로 가는 경우 ( 왼 -> 오른쪽으로 온거) 
                fuel[i+1][j][1]=fuel[i][j][2]+road[i+1][j]

            else:
                # 왼쪽으로 간다면 
                fuel[i+1][j-1][0]=min(fuel[i][j][1],fuel[i][j][2])+road[i+1][j-1]
                # 가운데로 간다면 
                fuel[i+1][j][1]=min(fuel[i][j][0],fuel[i][j][2])+road[i+1][j]
                # 오른쪽으로 간다면
                fuel[i+1][j+1][2]=min(fuel[i][j][0],fuel[i][j][1])+road[i+1][j+1]

result=601
for i in fuel[-1]:
    result=min(result,min(i))
print(result)

😎친구의 풀이

from copy import deepcopy
def main():
    result = 999
    for stage in range(1,n):
        for k in range(m):
            if k < m-1:# 우측에서 온걸 가져올건데 우측것만 아니면 좋겠어.
                dp[stage][k][2] = min(dp[stage][k][2],dp[stage-1][k+1][1] + zido[stage][k],dp[stage-1][k+1][0] + zido[stage][k])
            if k > 0: # 좌측에서 온걸 가져올건데 좌측것만 아니면 좋겠어.
                dp[stage][k][0] = min(dp[stage][k][0],dp[stage-1][k-1][1] + zido[stage][k],dp[stage-1][k-1][2] + zido[stage][k])
            # 바로 아래로 내려올건데 바로 아래서 내려온게 아니었음 좋겠어.
            dp[stage][k][1] = min(dp[stage][k][1],dp[stage-1][k][0] + zido[stage][k],dp[stage-1][k][2] + zido[stage][k])
    for i in dp[-1]:
        result = min(result,min(i))
    return result

if __name__ == '__main__':
    n,m = map(int,input().split())
    zido = [list(map(int,input().split())) for _ in range(n)]
    dp = [[[i,i,i] for i in zido[0]]]
    for i in range(n-1):
        dp.append([[999,999,999] for _ in  range(m)])
    # for i in dp:
    #     print(i)
    # print('asdasda',dp[-1])
    # exit()
    result = main()
    print(result)

# k 가 0이면 0이랑 1
# k 가 len-1이면 len-1 이랑 len-2
'''
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
'''