다이나믹 프로그래밍: 금광
문제정의
- n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져있으며, 각 칸은 특정한 크기의 금이 들어있습니다.
- 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m-1 번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야합니다.
- 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
입력조건
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n, m <= 20)
- 둘째줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 100)
출력조건
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다.
입출력예시
#입력1
3 4
1 3 3 2 2 1 4 1 0 6 4 7
#출력1
19
#입력2
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
#출력2
16
정답코드
n, m = map(int, input().split())
array = list(map(int, input().split(" ")))
n = 3
m = 4
array = [1,3,3,2
,2,1,4,1
,0,6,4,7]
dp = []
idx = 0
for i in range(n):
dp.append(array[idx:idx+m])
idx += m
for j in range(1, m): # 두번째 열부터 마지막열까지
for i in range(n): # 첫번째 행부터 마지막 행까지
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
# 왼쪽 위에서 오는 경우
if i == 0 : left_up = 0 # 위쪽 벽 넘으면 0
else: left_up = dp[i-1][j-1]
# 왼쪽 아래에서 오는 경우
if i == n-1 : left_down = 0 # 아래쪽 벽 넘으면 0
else: left_down = dp[i+1][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)
로직
- 금광의 모든 위치에 대해 다음 세가지만 고려합니다.
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
- 받는 쪽의 관점으로 문제를 해석하고, 위 세가지 경우에서 가장 많은 금을 가지고 있는 경우를 dp 테이블에 갱신합니다.
- array에 있는 값을 dp[i][j]로 표현합니다.
- 점화식은 다음과 같습니다.
- dp[i][j] = dp[i][j] + max(dp[i-1][j-1], dp[i+1][j-1], dp[i][j-1])
- 테이블을 벗어나지 않는지 체크가 필요합니다.
- 편의상 초기 데이터를 담는 array변수를 사용하지 않고 dp 테이블을 활용해도 됩니다.
Author And Source
이 문제에 관하여(다이나믹 프로그래밍: 금광), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yozzum/다이나믹-프로그래밍-금광저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)