[다이나믹 프로그래밍] 이코테 (파이썬) 금광 풀이

[문제]

n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다.

 

채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다.

 

이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다.

 

결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

 

[입력 조건]

1. 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)

 

2. 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n, m <= 20)

 

   둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 100)

 

[출력 조건]

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

<입력 예시>
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
<출력 예시>
19
16

 

[풀이]

for tc in range(int(input())) :
  n, m = map(int, input().split())
  arr = list(map(int, input().split()))
  dp = []
  index = 0
  for i in range(n) :
    dp.append(arr[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_down, left)

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

 

먼저 테스트 케이스를 입력받은 후 입력받은 테스트 케이스만큼 반복문을 수행한다.

 

첫번째 반복문 내에서는 금광 정보를 입력받고 다이나믹 프로그래밍을 위한 2차원 테이블(dp)을 초기화한다.

 

금광 정보를 입력받을 때 한줄에 쭉 이어져서 입력되기 때문에 열의 크기 즉, m 단위로 데이터를 슬라이싱하여 dp 테이블에

 

담아주는 방식으로 수행한다.

 

그 후에 다이나믹 프로그래밍을 수행해주는데, 열 기준으로 각 데이터를 확인하면서 테이블을 갱신한다.

 

매 열을 하나씩 확인하여 각 열마다 전체 행을 확인하면서 모든 위치에 대하여 왼쪽 위에서 오는 경우와

 

왼쪽 아래에서 오는 경우, 그리고 왼쪽에서 오는 경우를 모두 확인하여 그 중에서 가장 큰 값을 구하고 현재 위치에 

 

매립되어 있는 금의 값을 더해서 현재 위치에 대한 값을 갱신해나간다.

 

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

 

위와 같이 다이나믹 프로그래밍을 수행하고 가장 오른쪽 열에 기록되어 있는 값 중에서 제일 큰 값을 찾아 출력하도록 한다. 

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저