백준 9465 < 스티커 > JavaScript

📍문제 링크

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

9465번: 스티커

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

- DP를 문제에 적용한다는 것은 메모이제이션이 활용된다는 것을 의미한다.

- 이 문제에 메모이제이션을 적용하려면, n=1, 2 ... 커질 때, n=1 일 때의 값이 n=2 일 때 활용되도록 하면 된다.

5 
3
최댓값 5

5 1
3 5
최댓값 10 (5+5)

5 1 10 
3 5  4
최댓값 20 (5+5+10)

그런데, 이런 경우도 있을 수 있다
5 1 4
3 5 10
최댓값 15 (5+10)

 

따라서 아래 처럼 n-1 or n-2 의 값을 고른 경우중 값이 큰 경우를 선택하는 이차원 배열을 만들어가면 된다

예제
5 1 10 2 4
3 5  7 1 6

n = 1 최댓값
5
3

n = 2
5 1 +3
3 5 +5

n = 3
n = 2의 최댓값 or n = 1의 최댓값중 골라서 사용 가능,

n = 2 활용 (선택)
5  4 10 +10
3 10  7 +4

n = 1 활용
5  4 10 +5
3 10  7 +3

 

📍의사 코드

- 예제로 주어진 이차원 배열을 data, 답을 기록할 이차원 배열을 memo라고 할 때,

- n = 1일 때 memo (data 컬럼1과 같음)

data[0][0]

data[1][0]

- n = 2일 때 memo

data[0][0], data[0][1] + data[1][0]

data[1][0], data[1][1] + data[0][0]

- n = 3일 때 memo

i) n = 1을 활용

data[0][0], data[0][1] + data[1][0], data[0][2] + data[1][0]

data[1][0], data[1][1] + data[0][0], data[1][2] + data[0][0]

ii) n = 2를 활용

data[0][0], data[0][1] + data[1][0], data[0][2] + data[1][1] + data[1][1] + data[0][0]

data[1][0], data[1][1] + data[0][0], data[1][2] + data[0][0] + data[0][1] + data[1][0]

 

정리하면,

data[0][0], data[0][1] + data[1][0], data[0][2] + max(data[1][0], data[1][1] + data[0][0])

data[1][0], data[1][1] + data[0][0], data[1][2] + max(data[0][0], data[0][1] + data[1][0])

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const tNum = +in1;
const answer = [];
for (let i = 0; i < tNum; i++) {
  const data = in2.splice(0, 3);
  const colNum = +data[0];
  const row1 = data[1].split(" ").map(Number);
  const row2 = data[2].split(" ").map(Number);
  const memo = Array.from({ length: colNum }, (_) => [0, 0]);
  memo[0][0] = row1[0];
  memo[0][1] = row2[0];
  for (let j = 1; j < colNum; j++) {
    if (j === 1) {
      memo[j][0] = row1[1] + row2[0];
      memo[j][1] = row2[1] + row1[0];
    } else {
      memo[j][0] = row1[j] + Math.max(memo[j - 2][1], memo[j - 1][1]);
      memo[j][1] = row2[j] + Math.max(memo[j - 2][0], memo[j - 1][0]);
    }
  }
  answer.push(Math.max(...memo[colNum - 1]));
}

console.log(answer.join("\n"));

 

📍리뷰

- splice를 사용하여 shift를 연달아 사용하여 데이터를 준비하는 것보다 복잡도를 낮췄다.

- 시간 복잡도를 더욱 낮춘 풀이를 보면, splice를 사용하지 않고, for 문으로 원본을 순회하며 별도의 배열에 저장하여 사용했다.