[이취코테] 금광

https://youtu.be/5Lu34WIx2Us

이 문제의 해설 영상이다.

문제

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

 

입력 조건

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

 

출력 조건: 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다.

 

정답 코드

import sys
t = int(sys.stdin.readline())
for _ in range(t):
    n, m = map(int, sys.stdin.readline().rstrip().split())
    data = list(map(int, sys.stdin.readline().rstrip().split()))

    dp = []
    index = 0
    for _ in range(n):
        dp.append(data[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)

이 문제는 2차원 테이블을 이용한 다이나믹 프로그래밍으로 해결할 수 있다.

 

금광의 모든 위치에 대하여 왼쪽 위에서 오는 경우, 왼쪽 아래에서 오는 경우, 왼쪽에서 오는 경우의 3가지 경우만 존재한다.

따라서 이 3가지 경우 중 최댓값을 테이블에 갱신해주며 문제를 해결할 수 있다.

 

따라서 점화식은 다음과 같다.

 

입력이 주어질 때 1차원으로 주어지기 때문에 이를 2차원 배열에 저장하기 위해 m 단위로 슬라이싱 하면서 저장해주어야 한다.

 

또한 배열을 순회할 때 행 단위가 아닌 열 단위로 데이터를 확인하면서 왼쪽 위에서 오는 경우, 왼쪽 아래에서 오는 경우, 왼쪽에서 오는 경우의 3가지 경우 중 최댓값을 현재 위치의 값에 더하면서 값을 갱신해나간다.

 

추가적으로 왼쪽 위에서 오는 경우와 왼쪽 아래에서 오는 경우는 인덱스를 벗어난다면 해당 값을 0으로 초기화해준다.

 

위와 같은 과정을 수행하고 가장 오른쪽 열의 값들 중에서 가장 큰 값을 출력한다.

 

 

느낀 점

입력받은 값을 그대로 dp 테이블로 사용한다는 점이 신기했다. 

풀이를 참고하긴 했지만 아이디어를 떠올리는 부분은 dp 문제 치고 어렵진 않았고 구현이 약간 귀찮은 부분이 많은 문제였던 것 같다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)