Chap 16. DP - Q31. 금광

  • 0
  • 0
0
0

1. 금광

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

A. 📜 문제

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

a. 예를 들면.

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

1332
2141
0647

가장 왼쪽 위의 위치를 (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

c. 🙄 회고

내 풀이

  • 처음에는 아주 단순하게 max값을 구하는 방식으로 풀었다가, 테스트 케이스 상 불가능한 부분을 발견하여 DP로 변경,

반성

  • 근데 내가 푼 방식이 올바른 DP는 아닌듯함.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

내가 푼 방식은 처음 위치에서 가능한 경우의 다음 위치를 각각 더하고 최댓값을 구하는 방식으로 진행했다.

심지어 DP 테이블로 사용하는 열을 하나만 만들어서 코드가 복잡해졌다.

차라리 공간복잡도를 조금 포기하고 DP 테이블을 array만큼 잡았더라면 코드가 개선되었을지도 모르겠다.

나동빈님 코드는 $a_{n+1} = max(a_{n | up}, a_{n | mid}, a_{n | down}) + a_{n+1}$ 공식을 사용하여 $a_{n+1}$에 올 수 있는 최댓값을 구하였다. 이 방식이 문제에서 제시하는 방식보다 더 빠를 것으로 생각된다.

a. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.