[JS] Q31 금광

Hadam Cho·2021년 4월 26일
1

Algorithm

목록 보기
27/32
post-custom-banner

문제

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

만약 다음과 같이 3 x 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만큼의 금을 채굴할 수 있으며, 이때의 값이 최댓값입니다.


입력

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


소스 코드

/*
1. 왼쪽 위에서 오는 경우
2. 왼쪽 아래에서 오는 경우
3. 왼쪽에서 오는 경우

dp[i][j] = array[i][j] + max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][i - 1])
*/

const T = 2;
const input = [
  [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]
];

for (let t = 0; t < T; t++) {
  const N = input[0][0];
  const M = input.shift()[1];

  const dp = [];
  let index = 0;
  for (let d = 0; d < N; d++) {
    dp.push(input[0].slice(index, index + M));
    index += M;
  }
  input.shift();

  for (let j = 1; j < M; j++) {
    for (let i = 0; i < N; i++) {
      let leftUp = 0, leftDown = 0;
      if (i !== 0) {
        leftUp = dp[i-1][j-1];
      }
      if (i !== N - 1) {
        leftDown = dp[i+1][j-1];
      }
      const left = dp[i][j-1];
      dp[i][j] = dp[i][j] + Math.max(leftUp, leftDown, left);
    }
  }

  let result = 0;
  for (let i = 0; i < N; i++) {
    result = Math.max(result, dp[i][M - 1]);
  }

  console.log(result);
}

느낀 점

아직 혼자 힘으로 해결할 수는 없을 것 같다. 다이나믹 프로그래밍이 어떻게 실제 기출문제에 적용이 되는지 느낌과 코드 스타일만 익히고 나중에 다시 풀어봐야 할 것 같다.

profile
(。・∀・)ノ゙
post-custom-banner

0개의 댓글