금광

💻 입력 조건

• 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)
• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n,m <= 20) 둘째 줄에 n x m 개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (0 <= 각 위치에 매장된 금의 개수 <= 100)

💻 출력 조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

💻 입력 예시

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

📖 문제 해결
다이나믹 알고리즘을 이용하여, 오른쪽 위, 오른쪽, 오른쪽 아래로 이동해가면서 해당 위치에서의 금광의 최댓값을 구해나가는 코드를 작성하여 문제를 해결하였습니다.
여기서 이중 반복문을 이용하기 위하여(문제를 해결하기 위해서는 한 열을 모두 계산하고 다음 열로 넘어가는 계산을 해야 하지만, 이중 반복문은 한 행을 모두 계산하고 다음 항으로 넘어가서 계산하므로) 금광의 위치 정보를 담고 있는 2차원 리스트를 시계 방향으로 90도 돌린 후 알고리즘을 적용하였습니다.
다이나믹 프로그래밍을 이용하여 계산을 모두 마쳤다면, 채굴자가 얻을 수 있는 금의 최대 크기는 마지막 row에서의 최댓값과 같으므로 max(d[-1])의 값을 출력할 수 있도록 하였습니다.

# 문제 해결을 위해 금광 list를 적절하게 변형
def list_transform(map_list,n,m):
    map_inform = [[] for i in range(m)]
    
    count = -1
        
    for idx, item in enumerate(map_list):
        count += 1
        count %= m
        map_inform[count].append(item)
    
    return map_inform

# 채굴자가 얻을 수 있는 금광의 최대 크기를 구하기 위한 다이나믹 알고리즘
def dynamic_algo(map_information, n, m):
    d = [[0] * n for i in range(m)]
    d[0] = map_information[0]

    for r_idx, row in enumerate(map_information):
        for c_idx, col in enumerate(row):
            # 현재 맨 왼쪽 줄을 기준으로 최댓값을 계산하는 경우
            if r_idx > 0 and c_idx == 0:
                d[r_idx][c_idx] = map_information[r_idx][c_idx] + max(d[r_idx-1][c_idx], d[r_idx-1][c_idx+1])

            # # 현재 맨 오른쪽 줄을 기준으로 최댓값을 계산하는 경우
            elif  r_idx > 0 and c_idx == n - 1:
                d[r_idx][c_idx] = map_information[r_idx][c_idx] + max(d[r_idx-1][c_idx], d[r_idx-1][c_idx-1])
            
            # 현재 맨 왼쪽 줄과 맨 오른쪽 줄이 아닌 위치를 기준으로 최댓값을 계산하는 경우
            elif  r_idx > 0:
                d[r_idx][c_idx] = map_information[r_idx][c_idx] + max(d[r_idx-1][c_idx], d[r_idx-1][c_idx-1], d[r_idx-1][c_idx+1])

	# 채굴자가 얻을 수 있는 금의 최대 크기(마지막 row에서의 최댓값) 구하기
    answer = max(d[-1])
        
    return answer

# t를 입력받기
t = int(input())

# 각 테스트 케이스 T마다 금의 최대 개수 계산 및 출력
for i in range(t):
    n, m = map(int,input().split())
    map_inform = list(map(int,input().split()))
    map_inform = list_transform(map_inform,n,m)
    print(dynamic_algo(map_inform, n, m))