[Algorithm] Dynamic Programming - ‘금광 문제’
📣 학습한 내용을 정리한 글입니다.
다이나믹 프로그래밍 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python
문제 설명
내용
N x M 크기의 금광이 있다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어있다.
채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작하는데, 맨 처음에는 어느 행에서든 출발할 수 있다.
이후에 m-1번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동이 가능하다.
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 테스트 케이스 T가 입력된다. (1 <= T <= 1000)
매 테스트 케이스 첫째 줄에는 N과 M이 공백을 구분되어 입력된다. (1 <= N, M <= 20)
N x M개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다.
출력
테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다.
문제 풀이
Dyanmic Programming Algorithm 참고내용
- 동적계획법이라고도 부르며, 최적 부분구조 및 중복되는 부분 문제의 조건에 맞게 출제된다.
- 통상적으로 점화식을 이용하며 bottom-up(상향식)방식으로 풀 수 있다.
- dp 테이블을 이용하여 점화식을 적용시켜 문제를 풀어간다.
위 참고사항을 준수하며, 풀어보자.
이차원 배열을 만들어 dp테이블을 구성한다.
new_values[i][j] = i행 j열에 존재하는 금의 양, dp[i][j] = i행 j열까지의 얻을 수 있는 금의 최댓값
점화식으로 dp[i] = new_values[i][j] + max(dp[i-1][j-1], dp[i][j-1] + dp[i+1][j-1]) 가 만들어 진다.
작성 코드
Python
참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍 영상
댓글남기기