[Algorithm] 금광 문제

이코테 p.375 '금광' 문제

문제

2차원 테이블에서 채굴자가 얻을 수 있는 금의 최대 크기를 구하는 문제이다.

내 실수

• 2차원 테이블의 맨 왼쪽부터 채굴자가 얻을 금을 하나씩 선택해서 이어가는 느낌으로 풀었다.
• 이건 행마다 max 값을 고르는 선택의 느낌으로 풀면 안 된다. (이러면 결국 그리디가 되어버린다)
• 어떤 선택이 최적해가 될 지 모르기 때문에 결국에는 모든 맵에 대해서 최적해를 구해주어야 한다.
• 점화식은 나름 비슷하게 세웠는데, 애초에 내 풀이는 가정이 잘못 됐다. ('선택' 의 느낌으로 갔기 때문)

이 문제를 해결하는데 DP 를 선택해야하는 이유

1. 최적 부분 구조인가 - YES
2. 중복되는가 - YES

 

for tc in range(int(input())):
    n, m = map(int, input().split())
    array = list(map(int, input().split()))

    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):  # 현재 타겟이 있는 행 인덱스
            # 왼쪽 위에서 오는 경우
            left_up = dp[i - 1][j - 1] if i != 0 else 0
            # 왼쪽 아래서 오는 경우
            left_down = dp[i + 1][j - 1] if i != n - 1 else 0
            # 왼쪽에서 오는 경우
            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)