15989 1,2,3더하기 4 node.js

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

접근방식

n이 10,000보다 작거나 같기 때문에, 모든 경우의 수를 탐색하면 시간이 터질 것 같았음. (10일때 14이니까, 100일때 100이라고 생각해도 1억번)

그래서 이건 무조건 dp다! 생각은했는데, 아무리 해도 규칙성을 모르겠다...

dp[1] = 1
dp[2] = 2 (1+1, 2)
dp[3] = 3 (1+1+1, 2+1, 3)
dp[4] = 4
...

우선 이런식으로 몇개 작성해봤는데, 규칙성을 찾기가 매우 어려웠고, 경우의 수가 너무 많아져서 제대로 구했는지 확인하기 어려웠습니다. 그래서 우선, 완전탐색 코드를 작성해서 dp[1]부터 dp[100]까지 값을 한번 출력해보았습니다.

완전 탐색 코드

const dp = [['1'], ['11', '2'], ['111', '12', '3']];
for (let i = 2; i < 100; i++) {
  const temp = [];
  for (let j = 0; j < 3; j++) {
    const newDp = dp[i - j].map((el) => {
      const splitted = el.split('');
      const tt = [...splitted, j + 1];
      tt.sort();
      return tt.join('');
    });
    newDp.forEach((el) => {
      if (temp.includes(el)) return;
      temp.push(el);
    });
  }

  dp.push(temp);
}

const newDp = dp.map((el) => el.length);
console.log(newDp);

출력값

[
    1,   2,   3,   4,   5,   7,   8,  10,  12,  14,  16,  19,
   21,  24,  27,  30,  33,  37,  40,  44,  48,  52,  56,  61,
   65,  70,  75,  80,  85,  91,  96, 102, 108, 114, 120, 127,
  133, 140, 147, 154, 161, 169, 176, 184, 192, 200, 208, 217,
  225, 234, 243, 252, 261, 271, 280, 290, 300, 310, 320, 331,
  341, 352, 363, 374, 385, 397, 408, 420, 432, 444, 456, 469,
  481, 494, 507, 520, 533, 547, 560, 574, 588, 602, 616, 631,
  645, 660, 675, 690, 705, 721, 736, 752, 768, 784, 800, 817,
  833, 850, 867, 884,
  ... 1 more item
]

흠... 자세히 보니 6개를 주기적으로 규칙성을 띄는걸 알 수 있습니다.

첫번째 사이클
1, 2, 3, 4, 5, 7, 8
두번째 사이클
10, 12, 14, 16, 19, 21
세번째 사이클
24, 27, 30, 33, 37, 40

n번째 사이클은 각각 +n씩 하다가 4번째 요소에서 5번째 요소로 넘어갈 때 +n+1이 되는 규칙성을 가지고 있더라구요. (왜 이런지는 모르겠음.)

암튼. N이 10,000까지 이 규칙성을 띄기를 바라면서 dp를 작성해봤습니다.

정답코드

---

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

const dp = [1];
let cnt = 1;
while (true) {
  for (let i = 0; i < 6; i++) {
    const prevDp = dp.at(-1);
    let next = 0;
    if (i === 4) next = prevDp + cnt + 1;
    else next = prevDp + cnt;
    dp.push(next);
  }
  cnt += 1;
  if (dp.length > 10000) break;
}

const N = Number(input[0]);
for (let i = 0; i < N; i++) {
  const target = Number(input[i + 1]);
  console.log(dp[target - 1]);
}

풀긴 했는데, 왜 이런 규칙성을 띄는지는 모르겠음...