백준을 생전 안 할 것 같았는데 블로그를 개설하고 나서 처음으로 문제 해결 글을 쓰게 됐다. 바로 앞 문제인 2748번은 다음과 같은 코드로 그냥 풀 수 있고 따라서 티어도 브론즈이다.

const wapas = Number(require('fs').readFileSync(0, 'utf8').trim());
const fibo = (n) => n < 2 ? 1 : fibo(n - 1) + fibo(n - 2);
console.log(fibo(wapas));

그런데 2749번은 골드 아니랄까봐 이걸로 절대 안 풀린다. 애초에 n이 1,000,000,000,000,000,000보다 작거나 같은 자연수여서 저렇게 넣는 순간 시간 초과가 뜬다.

그럼 어떻게 풀어야 할까? 생각해본 방법이 두 가지가 있었는데 결국에는 마지막 방법을 사용해서 풀었다.

1과 0만 저장하기

어차피 피보나치 수열이 0, 1, 1, 2, 3, 5, 8, … 식으로 가기 때문에 0과 1은 어떻게든간에 호출을 하게 되어있다. 8을 계산하기 위해서는 5가, 5를 계산하기 위해서는 3이, 3을 계산하기 위해서는 2가, 그 다음엔 1, 0이 각각 필요해진다.

const wapas = Number(require('fs').readFileSync(0, 'utf8').trim());
const initial = [0, 1];
const fibo = (n) => initial[n] ?? fibo(n - 1) + fibo(n - 2);
console.log(fibo(wapas));

되기…는 개뿔 40번째 피보나치 수를 계산하는 데만 1초 가까이 소요가 됐다. 1,000,000,000,000,000,000을 갖다박으면 죽었다 깨나도 못 풀 거다.

Dynamic Programming

다시 처음으로 돌아가서 생각을 해보면, 피보나치 수열의 n번째 수는 얼마인가? 를 묻는 질문에 답을 하려면, 실제로 반복문이든 재귀함수든 돌려야 하는 건 맞지만 최종적으로는 n – 1번째 수와 n – 2번째 수만 알고 있으면 된다.

const wap = BigInt(require('fs').readFileSync(0, 'utf8').trim());
console.log(wapas(wap).toString());

function wapas(f) {
  let [wa, pas] = [1n, 0n];
  for (let w = 0; w < f; w++) {
    [wa, pas] = [(wa + pas) % 1_000_000n, wa];
  }
  return pas;
}

그래서 이렇게 짜봤다. 우선 정확한 계산을 위해 BigInt로 변환을 하고, 이를 함수 wapas()로 넘긴다.

함수 wapas(f)에서는 각각 wa, pas 변수의 초기값을 1n, 0n (BigInt끼리의 계산을 위함)으로 선언하고, for 루프를 돌려 w가 f보다 작은 동안 wa, pas 변수의 값을 갱신해준다.

이 때의 wa는 피보나치 수열의 1번째 값인 1, pas는 0번째 값인 0이 되며, 이로부터 2번째 값을 구할 수 있으므로, for 루프 안에서 wa는 wa + pas (n + 1번째 값), pas는 이전의 wa (n번째 값)로 갱신시켜준다. 2749번 문제의 조건은 1,000,000으로 나눈 나머지이므로 아예 나눠서 저장한다.

그리고 pas의 값을 리턴해주면 된다. 사실 이건 for 루프를 w가 0일 때부터 돌린 거라서, 1 <= w <= f일 동안 돌리고 pas 대신 wa를 리턴해줘도 된다.

그런데 이렇게 해도 시간 초과가 뜨는데, 역시 그 더럽게 큰 n이 문제다. 굳이 결과를 1,000,000으로 나누라고 한 이유가 있을 것 같아서 반복되는 부분을 찾아봤다.

아니나 다를까 1,500,000번째 피보나치 수를 1,000,000으로 나눈 나머지가 0이다. 그럼 반복문을 돌릴 조건을 “w가 f를 1,500,000으로 나눈 나머지보다 작을 때”로 수정하면 되겠다.

const wap = BigInt(require('fs').readFileSync(0, 'utf8').trim());
console.log(wapas(wap).toString());

function wapas(f) {
  let [wa, pas] = [1n, 0n];
  for (let w = 0; w < (f % 1_500_000n); w++) {
    [wa, pas] = [(wa + pas) % 1_000_000n, wa];
  }
  return pas;
}

2번의 시간 초과, 1번의 런타임 에러 끝에 정답이라는 결과를 받았다.