Q31. 금광

문제

<이코테 Q31번>

풀이

이 문제는 인덱스가 넘어가지 않게 문제를 푸는 것이 키 포인트이다.
1. 이를 위해서 맨 위에서 오는 경우, 맨 아래 인덱스에서 오는 경우를 제외해주어야 한다.
또한 왼쪽에서 오른쪽으로 금광을 캐므로 평소에 2차원 리스트 for문을 돌릴 때와는 반대로 돌려주어야 한다.
2. for문을 돌리며 인덱스를 왼쪽에서 오른쪽으로 움직여주자.

for 문을 적용하면

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

이렇게 된다. 그러니까 왼쪽 위, 왼쪽 아래, 왼쪽에서 오는 경우를 모두 고려해서 최댓값을 내주는 방식이다.

여기서 인덱스가 범위를 넘어가는 경우를 예외처리해주면 최댓값을 선택해주는 경우의 코드는 이렇게 작성된다.

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] += max(left_up, left_down, left)

이 때 dp테이블은 결과값을 저장하는 테이블로, 받은 데이터값을 초기화 해준 테이블이다. 다음과 같이

dp = []
index = 0
for i in range(n):
    dp.append(array[index: index+m])
    index += m

array값을 2차원 리스트로 저장한 형태이다. 이 dp테이블을 출발한 금광에 따라 출력해보기 위해선 역시 for문을 돌려서 출력해보면 된다.

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

다이나믹 프로그래밍에선 dp테이블을 어떻게 사용하느냐가 가장 큰 문제이니 열심히 활용해보도록하자..