티스토리 뷰

코딩테스트

금광

ajaa 2024. 12. 16. 09:45

📌문제

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

 

📌풀이

2차원 테이블을 이용한 다이나믹 프로그래밍

1. 왼쪽 위에서 오는 경우

2. 왼쪽 아래에서 오는 경우

3. 왼쪽에서 오는 경우

이 3가지 경우 중 가장 많이 금을 가지고 있는 경우를 테이블에 저장

 

📌코드

for tc in range(int(input())):
    # 금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int, input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    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):
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우
            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)

 

📌참고

https://g.co/kgs/eyd5SSd

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

IT 취준생이라면 누구나 입사하고 싶은 카카오・삼성전자・네이버・라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다! IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년

www.google.com

 

 

'코딩테스트' 카테고리의 다른 글

병사 배치하기  (0) 2024.12.18
정수 삼각형  (0) 2024.12.17
가사 검색  (1) 2024.12.15
공유기 설치  (0) 2024.12.13
고정점 찾기  (1) 2024.12.12
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함