[이것이 코딩 테스트다] 다이나믹 프로그래밍 - 금광

YEAh·2021년 3월 24일

이것이 코딩 테스트다

목록 보기

30/39

다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

✅ 문제

n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 촐력하는 프로그램을 작성하세요.

입력 예시

2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력 예시

19
16

💻 코드

def gold_func(n, m, data):
 
    d = [[0] * m for _ in range(n)] 

    for i in range(n):
        d[i][0] = data[i][0]
        
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 아래가 금광 범위를 넘지 않는다면
            if i+1 < n:
                temp = data[i][j] + d[i+1][j-1]
                d[i][j] = max(d[i][j], temp)
            # 왼쪽 위가 금광 범위를 넘지 않는다면
            elif i-1 >= 0:
                temp = data[i][j] + d[i-1][j-1]
                d[i][j] = max(d[i][j], temp)
            # 왼쪽
            temp = data[i][j] + d[i][j-1]
            d[i][j] = max(d[i][j], temp)
    max_list = []

    for i in range(n):
        max_list.append(max(d[i]))

    print(max(max_list))
    

T = int(input())

for i in range(T):
    n, m = map(int, input().split())
    input_data = list(map(int, input().split()))
    
    data = []

    for i in range(0,len(input_data),4):
        data.append(input_data[i:i+4])

    gold_func(n, m, data)

설계

1열부터 m열까지 최대로 캘 수 있는 금의 크기를 2차원 배열 d에 저장한다. 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동할 수 있으므로 금의 크기를 최대로 하기 위해 현재 금광에서 왼쪽 위, 왼쪽, 왼쪽 아래의 금을 더한 것 중에 최댓값을 d에 저장한다. 그러면 m열에서 최댓값이 최대로 캘 수 있는 금의 크기이다.

➕ 다른 풀이

문제 접근 방식은 같지만 더 깔끔한 풀이법.

내 풀이법은 왼쪽 위, 왼쪽, 왼쪽 아래의 값 비교할 때 왼쪽 위와 더한 값을 왼쪽과 더한 값과 비교하는 식으로 일단 더해 놓고 다음에 더한 값과 최댓값을 비교하였다.
하지만 이 방식은 자신의 왼쪽 위, 왼쪽, 왼쪽 아래 값을 비교하고 최댓값을 더하였다.

for t in range(int(input())):
    n, m = map(int, input().split())

    array = list(map(int, input().split()))

    data = []
    index = 0
    for i in range(n):
        data.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 = data[i-1][j-1]
            # 왼쪽 아래에서 오는 경우
            if i == n - 1 :
                left_down = 0
            # 왼쪽에서 오는 경우
            else:
                left_down = data[i+1][j-1]
            left = data[i][j-1]
            data[i][j] = data[i][j] + max(left_up, left_down, left)
    
    result = 0
    for i in range(n):
        result = max(result, data[i][m-1])
    print(result)