[JS][백준]1749_점수따먹기

문제 번호

1749번: 점수따먹기

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘
• 누적 합

 

문제 풀이

 2차원 배열을 활용한 누적합을 사용해야 한다. 그리고 그 누적합들을 모두 살펴보면서 가장 큰 값을 갖는 영역을 찾아야 한다. 

 

 우선 2차원 배열을 사용한 누적합이 잘 기억이 안나서 해당 부분만 찾아보았다.

2차원 배열을 사용한 누적합은 가로로의 합, 세로로의 합을 모두 구해야 한다. 따라서 문제에서 주어진 게임판의 크기보다 가로 세로가 1칸씩 더 킨 sum 배열을 만들어서 누적합을 저장할 준비를 했다.

const arr = input.slice(1).map(_ => _.trim().split(' ').map(Number));
let sum = new Array(N + 1).fill(null).map(_ => new Array(M + 1).fill(0))

 

이제 sum배열에 가로로, 세로로 합을 모두 구해서 2차원 누적합을 만들어 주어야한다.

function makeSum(N, M, arr, sum) {
   for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
         sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i - 1][j - 1]
      }
   }
   return sum;
}

sum을 만드는 식은 그냥 외워서 사용하는 게 더 편할지도 모르겠다.

 

 아무튼, 이제 만들어진 2차원 배열 sum을 갖고 가장 큰 합을 갖는 영역을 찾아야 한다. 찾는 방법은 브루트포스로 모든 영역을 다 검사해보면 된다. 2차원 배열의 부분 영역의 합을 구하는 방법은 다음과 같다.

https://data-make.tistory.com/399

[BOJ] 2167. 2차원 배열의 합(DP, 누적합).py.cpp

 

 위의 설명대로 영역의 넓이를 구해본다. 이때 2차원 배열에 있는 숫자들이 모두 다 음수일 수 도 있다. 따라서 answer의 초기값은 -Infinity로 두고 구해야 한다.

function sol(N, M, sum) {
   let answer = -Infinity;

   for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
         let [y, x] = [i, j];
         // x,y는 시작점이고 col,row 까지 범위에 있는 영역의 넓이를 구한다.
         for (let row = y; row <= N; row++) {
            for (let col = x; col <= M; col++) {
               let area = sum[row][col] - (sum[row][x-1]) - (sum[y-1][col]) + sum[y-1][x-1]               
               if(area > answer)
                  answer = area;
            }
         }
      }
   }
   return answer;
}

 

전체 코드

function main() {
   let answer = 0;
   const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
   const [N, M] = input[0].trim().split(' ').map(Number);
   const arr = input.slice(1).map(_ => _.trim().split(' ').map(Number));
   let sum = new Array(N + 1).fill(null).map(_ => new Array(M + 1).fill(0))

   sum = makeSum(N, M, arr, sum);   
   answer = sol(N,M,sum);

   return console.log(answer);
}
function makeSum(N, M, arr, sum) {
   for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
         sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i - 1][j - 1]
      }
   }
   return sum;
}
function sol(N, M, sum) {
   let answer = -Infinity;

   for (let i = 1; i <= N; i++) {
      for (let j = 1; j <= M; j++) {
         let [y, x] = [i, j];
         // x,y는 시작점이고 col,row 까지 범위에 있는 영역의 넓이를 구한다.
         for (let row = y; row <= N; row++) {
            for (let col = x; col <= M; col++) {
               let area = sum[row][col] - (sum[row][x-1]) - (sum[y-1][col]) + sum[y-1][x-1]               
               if(area > answer)
                  answer = area;
            }
         }
      }
   }
   return answer;
}
main();

특이사항

2차원 배열을 사용한 누적합을 많이 사용해보지 않아서 알고리즘을 떠올리고 나서도 구현하는데 시간이 오래 걸렸다.