[이코테/다이나믹프로그래밍/DP] 금광(정답,풀이)

문제

- n x m 크기의 금광의 각 칸은 특정한 크기의 금이 들어 있음
- 채굴자가 첫 번째 열부터 출발해 금을 캠
- 첫 번째 열의 어느 행에서든 출발할 수 있고, 이후 m번에 걸쳐 매번 오른쪽위/오른쪽/오른쪽 아래로의 이동을 수행
- 채굴이 끝난 후 채굴자가 얻을 수 있는 금의 최대 크기 출력

정답

for tc in range(int(input())):
    n,m = map(int,input().split())
    array = list(map(int,input().split()))

    dp =[]
    index = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index+=m
    
    # dp[i][j] 칸 = 왼쪽 위/왼쪽/왼쪽 아래 세 개의 값 중 가장 큰 값. 
    for j in range(1,m):
        for i in range(n):
            if i == 0: # 맨 윗줄 -> 왼쪽 위는 들어올 수 없음
                left_up=0
            else:
                left_up=dp[i-1][j-1]
            if i == n-1: # 제일 아랫줄 -> 왼쪽 아래에서는 들어올 수 없음
                left_down = 0
            else:
                left_down = dp[i+1][j-1]

            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up,left_down,left)
    
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])

    print(result)

 

풀이

아무래도 DP문제인걸 알고 접근하니 푸는 아이디어는 금방 생각했다.

이전의 값+내 값을 더했을 때 가장 큰 값을 계속해서 선택해 나가는거였는데,

 

처음에 나는 첫 열부터 시작해서 둘째 열, 셋째 열 ... 마지막 열까지 세로로 반복문을 돌려야 된다고 생각했고

내 값 + 다음 이동 후의 값을 다음 칸에 저장시키고, 내 밑의 열에서도 밑의 열 + 다음 이동 후 값을 다음 칸에 저장

(이 때 이전에 가지고 있던 값과 비교해 큰 값 저장)시키는 로직을 생각했는데, 

 

답지에서는 array[I][j]가 있을 때, 그 값은 왼쪽 상단/ 왼쪽/ 왼쪽 하단 세 군데에서 들어올 수 있으니

내 값 + 들어올 수 있는 가장 큰 값을 계속해서 더해나가는 로직을 구현했다.

 

아래는 도출된 점화식.

dp[i][j] = dp[i][j] + max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])

이 때, 열의 인덱스가 0이면 왼쪽 상단에서는 들어올 수 없으므로 0 으로 초기화, 

마찬가지로 열의 인덱스가 n-1이면 왼쪽 하단에서는 들어올 수 없으므로 0으로 초기화한다.

 

모든 로직을 반복한다면 테이블에는 각 칸을 거칠 때 가장 금을 많이 캘 수 있는 금의 크기가 저장되어 있을 것임.

그리고 제일 끝 dp[i][-1] 의 값들 중 가장 큰 값을 출력하면 된다.!!!

 

 

 

역시 DP에서는 점화식을 떠올리는게 중요하다는 생각을 했다!

 

 

 

참고

이것이 취업을 위한 코딩테스트다(with.python)