Chap 16. DP - Q31. 금광

@mildsalmon·2021-10-21 07:47

1. 금광

난이도
- 중하
풀이 시간
- 30분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- Flipkart 인터뷰

A. 📜 문제

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

a. 예를 들면.

3 * 4 크기의 금광이 존재한다고 가정하자.

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

가장 왼쪽 위의 위치를 (1, 1), 가장 오른쪽 아래의 위치를 (n, m)이라고 할 때, 위 예시에서는 (2, 1) -> (3, 2) -> (3, 3) -> (3, 4)의 위치로 이동하면 총 19만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값이다.

b. 입력 조건

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

c. 출력 조건

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

d. 테스트 케이스

입력 예시


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
```

B. 💡 내 답안

a. 😊 1차 시도 (성공)


T = int(input())
col_row = []
array = [[] for i in range(T)]

for j in range(T):
    row, col = list(map(int, input().split()))

    col_row.append((row, col))

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

    for i in range(row):
        array[j].append(temp[i*col:(i*col)+col])

dp = []
answer = []
for i, c_r in enumerate(col_row):
    row, col = c_r
    dp.append([0] * row)
    
    for r in range(row):
        dp[-1][r] = array[i][r][0]
        next_r_pos = r
        for c in range(1, col):
            next_r_value = 0
            
            if next_r_pos-1 >= 0:
                if next_r_value < array[i][next_r_pos-1][c]:
                    next_r_value = array[i][next_r_pos-1][c]
                    next_r_save = next_r_pos - 1
                    
            if next_r_pos+1 < row:
                if next_r_value < array[i][next_r_pos+1][c]:
                    next_r_value = array[i][next_r_pos+1][c]
                    next_r_save = next_r_pos + 1
                    
            if next_r_value < array[i][next_r_pos][c]:
                next_r_value = array[i][next_r_pos][c]
                next_r_save = next_r_pos
                
            next_r_pos = next_r_save
            dp[-1][r] += next_r_value

    answer.append(max(dp[-1]))

print(*answer, sep='\n')

# 1시간 5분 56초

b. 😊 2차 시도 (성공)


for t in range(int(input())):
    n, m = list(map(int, input().split()))
    temp = list(map(int, input().split()))
    array = [[0] * m for i in range(n)]

    for i in range(n):
        for j in range(m):
            array[i][j] = temp[(i * m) + j]

    # dp = [0] * (n * m)
    dp = [[0] * m for i in range(n)]

    for i in range(n):
        # i = 0, 1, 2
        # 필요한 수 = 0, 4, 8
        # column_number = m * i
        #
        # dp[column_number] = array[column_number]
        dp[i][0] = array[i][0]

    for i in range(1, m):
        for j in range(n):
            if j-1 < 0:
                left_up = 0
            else:
                left_up = dp[j-1][i-1]

            if j+1 >= n:
                left_down = 0
            else:
                left_down = dp[j+1][i-1]

            left = dp[j][i-1]

            dp[j][i] = max(left_up, left, left_down) + array[j][i]

        answer = 0

        for j in range(n):
            answer = max(dp[j][i], answer)

    print(answer)


# 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