[다이나믹 프로그래밍] ▲ 문제5 - 금광(52:30)

[이코테] 문제5 - 금광(52:30)

(한줄평) 혼자서 푸는데는 성공했지만 책 코드와 약간 다른 부분이 있어 복습이 필요한 문제!!

---

---

(풀이1) 내 풀이 틀린 코드(1차원 리스트)

풀이 시간: 50분 이내

1) 문제 해결 아이디어

문제 자체는 2차원 리스트이지만 입력을 1차원 리스트로 받았기 때문에 금의 최대 크기를 담은 dp테이블도 1차원 리스트로 생성하여 풀었다.

 

2) 소스코드

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  n, m = map(int, input().split())  # 세로, 가로
  graph = list(map(int, input().split()))  # n * m 개의 금 개수
  d = [0] * (n * m)  # 금의 최대 크기

  for i in range(n*m):
    # 0열 초기화
    if i % m == 0:
      d[i] = graph[i]
    # 마지막 열이 아니면
    if i % m != 3:
      # 1. 오른쪽
      if 0 <= i + 1 < n * m:
        d[i + 1] = max(d[i + 1], d[i] + graph[i + 1])
      # 2. 오른쪽 위
      if 0 <= i + 1 - m < n * m:
        d[i + 1 - m] = max(d[i + 1 - m], d[i] + graph[i + 1 - m])
      # 3. 오른쪽 아래
      if 0 <= i + 1 + m < n * m:
        d[i + 1 + m] = max(d[i + 1 + m], d[i] + graph[i + 1 + m])

res = 0  # 채굴자가 얻을 수 있는 금의 최대 크기
for i in range(m - 1, n*m, m):
  res = max(res, d[i])
print(res)

[출처] https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 

(풀이2) 책 풀이(2차원 리스트)

풀이 시간: 분 이내

1) 문제 해결 아이디어

기본적인 아이디어는 똑같지만 여기서는 1차원 리스트로 입력받은 것을 2차원 리스트(array)로 만들고 금의 최댓값을 담을 리스트를 2차원 리스트(d)로 생성했다는 점이 다르다.

 

<금광의 모든 위치에서 3가지 경우>

0열은 시작하는 위치로 이전값이 없고 자기 자신의 값을 그대로 취하면 되므로 1 ~ (m - 1)열에 대해 진행한다. 다음과 같이 

1. 왼쪽 위에서 오는 경우

0행일 경우, 왼쪽 위는 인덱스 범위를 벗어나기 때문에 왼쪽 위값(left_up)을 0으로 하고

0행이 아닌 경우, 왼쪽 위 값을 취한다.

2. 왼쪽에서 오는 경우

왼쪽은 어느행이든 간에 모든 값이 존재하므로 왼쪽 값을 그냥 취하면 된다.

3. 왼쪽 아래에서 오는 경우

마지막(m-1)행일 경우, 왼쪽 아래는 인덱스 범위를 벗어나기 때문에 왼쪽 아래값(left_down)을 0으로 하고

마지막(m-1)행이 아닐 경우, 왼쪽 아래값을 취한다.

주의할 점은 위에 코드처럼 좌표의 범위가 유효할 때만 검사하도록 해야한다. 그렇지 않으면 IndexError가 나니 주의하자! 

 

3가지 경우에서 나온 값들 (left_up, left, left_down 중 최댓값 + 현재칸의 금 개수)가 현재칸까지 얻을 수 있는 금의 최댓값이다.

 

<점화식>

 

2) 소스코드

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  n, m = map(int, input().split())  # 세로, 가로
  array = list(map(int, input().split()))  # n * m 개의 금 개수
  d = []  # n * m(2차원 dp 테이블)
  j = 0
  for i in range(n):
    d.append(array[j:j + m])
    j += m

  # 한 열씩 진행
  for j in range(1, m):
    for i in range(n):
      # 1. 왼쪽 위에서 오는 경우
      if i == 0:  left_up = 0  # 왼쪽 위 값 없음
      else:   left_up = d[i - 1] [j - 1]  # 왼쪽 위 값
      # 2. 왼쪽에서 오는 경우
      left = d[i][j - 1]  # 왼쪽 값
      # 3. 왼쪽 아래에서 오는 경우
      if i == n - 1:  left_down = 0  # 왼쪽 아래 값 없음
      else:  left_down = d[i + 1][j - 1]  # 왼쪽 아래값

      # i행 j열까지 얻을 수 있는 금의 최댓값 계산
      d[i][j] = d[i][j] + max(left_up, left, left_down)
  res = 0  # 채굴자가 얻을 수 있는 금의 최대 크기
  for i in range(n):
    res = max(res, d[i][m - 1])
  print(d)
  print(res)