백준 js 1932번

 

<문제>

https://www.acmicpc.net/problem/1932

 

 

 

<문제 핵심>

1. 동적 계획법을 사용하는 문제였고 아래로 내려가면서 큰 값을 더해나가 최대 누적합을 구하는 문제이다. 최대 누적합을 경우는 크게 문제에서 고려해야하는 3가지의 경우가 있었는데 다음과 같다.

 

예시로 다음과 같은 정삼각형 구조라 생각해보자

 

 

💡 왼쪽 전구 처럼 맨 왼쪽에 위치한 동그라미의 누적합을 구하는 경우

 ➡️ 이때는 본인 기준 오른쪽 대각선 에서만 누적합을 구할 때 이용할 수 있다.

💡 오른쪽 전구 처럼 맨 오른쪽에 위치한 동그라미의 누적합을 구하는 경우

 ➡️ 이때는 본인 기준 왼쪽 대각선 에서만 누적합을 구할 때 이용할 수 있다.

💡 가운데 전구 처럼 가운데에 위치한 동그라미의 누적합을 구하는 경우

 ➡️ 이때는 왼쪽 대각선, 오른쪽 대각선 둘 다 가능하고 두 가지중 누적합이 가장 큰 경우를 선택하면 된다.

 

문제로 돌아와서 문제를 보면 삼각형의 마지막 가로는 

4   5   2   6   5

 

다음과 같고 최종적으로 마지막 가로에서 가장 큰 누적합을 구하면 되는 문제였다. 위에서 설명한것을 적용해보자면 5,2,6은 왼쪽, 오른쪽 대각선을 고려해야 하고 4는 오른쪽 대각선, 맨 오른쪽의 5는 왼쪽 대각선을 고려해야 한다.

 

 

2. 점화식 또한 유추할 수 있는데 맨 왼쪽에 위치한 경우 행은 줄고 열은 그대로인 [i-1][j]와 같고 맨 오른쪽에 위치한 경우 행과 열이 모두 줄어든 [i-1][j-1], 가운데에 위치한 경우는 행과 열이 모두 줄어든 경우인 [i-1][j-1]과 행만 줄어든 경우인 [i-1][j] 중 큰 값으로 선택해야 한다. 

 

그리고 선택한 것과 현재 위치에 해당하는 값을 더하여 누적합을 계산한다.

 

만약 pyramid[2][0[을 구해야한다 생각해보자. 그럼 pyramid[1][0]의 값에서 pyramid[2][0]의 값을 더하면 되는데 pyramid[1][0]의 값은 누적합(10)이 구해져있으므로 해당 값을 그대로 이용한다. 여기서 동적 계획법의 특징인 동일한 작은 문제가 반복해서 등장하는 것을 확인할 수 있다.

if (j === 0) {
  pyramid[i][j] = pyramid[i - 1][j] + pyramid[i][j];
} else if (j === pyramid[i].length - 1) {
  pyramid[i][j] = pyramid[i - 1][j - 1] + pyramid[i][j];
} else {
  pyramid[i][j] =
    Math.max(pyramid[i - 1][j - 1], pyramid[i - 1][j]) + pyramid[i][j];
}

 

<문제 풀이과정 및 순서도>

 

1.  입력받을 피라미드를 담기위한 2차원 배열을 만들고 배열의 각 요소에 피라미드에 들어갈 값들을 채운다. 채워지면 배열은 다음과 같이 채워질 것이다.

피라미드

 

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = parseInt(input[0]);
const pyramid = Array.from({ length: n }, () => Array(n).fill([]));

// 피라미드 만들기
for (let i = 1; i <= n; i++) {
  const curRow = input[i].split(" ").map(Number);
  pyramid[i - 1].push(...curRow);
}

 

 

2. 기본적으로 첫 행은 모든 경우에서 사용되기 때문에 반복문 사용시 제외하고 구현한다. 이후 각 행마다 접근하여 열에 따라 조건문을 적용하는데 맨 왼쪽에 위치하는 경우와 맨 오른쪽에 위치하는 경우, 그리고 가운데에 위치하는 경우에 따라서 누적합을 계산한다. 이후 마지막 변에서 가장 큰 누적합의 경우를 구하여 출력한다.

 

for (let i = 1; i < n; i++) {
  for (let j = 0; j < pyramid[i].length; j++) {
    if (j === 0) {
      pyramid[i][j] = pyramid[i - 1][j] + pyramid[i][j];
    } else if (j === pyramid[i].length - 1) {
      pyramid[i][j] = pyramid[i - 1][j - 1] + pyramid[i][j];
    } else {
      pyramid[i][j] =
        Math.max(pyramid[i - 1][j - 1], pyramid[i - 1][j]) + pyramid[i][j];
    }
  }
}

console.log(Math.max(...pyramid[n - 1]));

 

<전체 코드>

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");

const n = parseInt(input[0]);
const pyramid = Array.from({ length: n }, () => Array(n).fill([]));

// 피라미드 만들기
for (let i = 1; i <= n; i++) {
  const curRow = input[i].split(" ").map(Number);
  pyramid[i - 1].push(...curRow);
}

for (let i = 1; i < n; i++) {
  // 가로 변
  for (let j = 0; j < pyramid[i].length; j++) {
    // 단위 개수
    if (j === 0) {
      // 제일 왼쪽
      pyramid[i][j] = pyramid[i - 1][j] + pyramid[i][j];
    } else if (j === pyramid[i].length - 1) {
      // 제일 오른쪽
      pyramid[i][j] = pyramid[i - 1][j - 1] + pyramid[i][j];
    } // 그 외
    else
      pyramid[i][j] =
        Math.max(pyramid[i - 1][j - 1], pyramid[i - 1][j]) + pyramid[i][j];
  }
}

console.log(Math.max(...pyramid[n - 1]));