1. 문제 설명
2. 문제 조건
- n은 3, m은 4
- 1 3 3 2
- 2 1 4 1
- 0 6 4 7
- 형태로 되어있다.
3. 문제 해결 아이디어
- 금광의 모든 위치에 대하여 다음의 세 가지만 고려
- 1. 왼쪽 위에서 오는 경우
- 2. 왼쪽 아래에서 오는 경우
- 3. 왼쪽에서 오는 경우
- 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결한다.
- 이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다.
4. 답안
#테스트 케이스 입력
for tc in range(int(input())):
#금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
#DP 테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[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)
'CodingTest > 다이나믹 프로그래밍' 카테고리의 다른 글
병사 배치하기 (0) | 2022.07.14 |
---|---|
효율적인 화폐 구성 (0) | 2022.07.14 |
1로 만들기 (0) | 2022.07.14 |
개미 전사 (0) | 2022.07.14 |
다이나믹 프로그래밍 개요 (피보나치 수열) (0) | 2022.07.13 |