[이코테] 다이나믹프로그래밍 - 금광

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

n x m 크기의 금광이 있다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력해라. 만약 다음과 같이 3 x 4 크기의 금광이 존재한다고 가정하자.

1	3	3	2
2	1	4	1
0	6	4	7

가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3, 3) -> (3, 4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며 이 때의 값이 최대값이 된다.

입력조건

• 첫째 줄에 테스트 케이스 T가 입력된다.(1 <= T <= 1,000)
• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 주어진다.(1 <= n, m <= 20) 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다.(1 <= 각 위치에 매장된 금의 개수 <= 100)

출력조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 각 테스트 케이스는 줄 바꿈을 이용해 구분한다.

사고과정

• 최댓값을 기록할 DP 테이블을 1차원 리스트에 한정해서 풀려고 했지만 풀지 못했다. 풀이를 볼 때 소스코드는 보지 않고 핵심적인 아이디어를 보았는데, DP 테이블을 2차원 리스트로 활용한 점을 보고 스스로 다시 소스코드를 구현한 결과, 책 속 풀이와 거의 유사하게 맞추었다. 핵심적인 아이디어가 관건인 듯 싶다..
• 문제에서는 오른쪽이라고 주어졌지만 m(행) 입장에서 보면 m-1 행에서는 왼쪽 위, 왼쪽, 왼쪽 아래로부터 DP 테이블의 이전 값이 들어오게 된다. 따라서 연습장에 그려서 점화식을 쉽게 알아낼 수 있었다.
• 책 속 풀이와 다르게 한 점은 필자는 업데이트할 DP 테이블 위치 인덱스가 행 값이 0 즉, 맨 위에있을 때랑 행 값이 n-1 즉, 맨 아래에 있을 때랑 가운데에 있을 때랑 if 조건문으로 점화식을 케이스를 나누어서 처리했음. 하지만 책 풀이는 하나의 점화식을 이용하되 맨 위, 아래에있을 때는 각각 왼쪽 위, 왼쪽 아래에서 오는 값을 0으로 설정해서 해주었음(멋지다..)
• 또 필자는 DP테이블과 주어진 금광 정보를 2차원 리스트로 받아서 2개의 array를 개별로 운영했는데, 책 풀이는 주어진 금광 정보를 애초에 DP테이블에 받아서 1열의 값부터 DP테이블을 갱신하는 방법으로 진행함(또 믓지다..)
• 추가적으로 그동안 2차원 리스트를 줄바꿈해서 입력받아서 따로 주어진 정보를 처리하는 데 어렵지 않았는데 이번 문제는 2차원 리스트에 들어갈 원소들을 1줄로 쭉 입력받아서 2차원 리스트에 내가 직접 넣어야 해서 이 부분에서도 시간이 걸렸음..이 로직도 책 속에서 인상적으로 구현하는데, index를 0으로 초기화해서 행 길이 m만큼 매번 더해서 index 값을 업데이트하면서 주어진 정보를 2차원 리스트에 담았음..

풀이(스스로 못 품)

1. 핵심 아이디어만 보고 내가 작성한 풀이

import sys

t = int(input())
for _ in range(2):
    n, m = map(int, input().split())
    array = list(map(int, input().split()))
    data = []
    for i in range(n):
        data.append(array[i*m:(i+1)*m])
    d = [[0] * m for _ in range(n)]
    for i in range(n):
        d[i][0] = data[i][0]

    for j in range(1, m):
        for i in range(n):
            # 가장 맨 위 자리
            if i == 0:
                d[i][j] = data[i][j] + max(d[i][j-1], d[i+1][j-1])
            # 맨 아래 자리
            elif i == n-1:
                d[i][j] = data[i][j] + max(d[i-1][j-1], d[i][j-1])
            # 중간 자리
            else:
                d[i][j] = data[i][j] + max(d[i-1][j-1], d[i][j-1], d[i+1][j-1])

    max_val = -1
    for i in range(n):
        max_val = max(max_val, d[i][m-1])

    print(max_val)

2. 책 속 풀이

이 풀이로 풀도록 하자!

 

import sys

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

    # DP 테이블과 주어진 금광 정보를 하나의 배열로 운영
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index += m  # 인덱스 센스..

    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, left_down)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    print(result)