[백준] 20500 Ezreal 여눈부터 가네 ㅈㅈ JavaScript

혅·2025년 1월 25일

JavaScript

백준, 프로그래머스 -JavaScript-

목록 보기

188/215

문제

욱제는 15라는 수를 굉장히 싫어한다. 그래서 0으로 시작하지 않고 1과 5로만 구성된 N자리 양의 정수 중에서, 15의 배수가 몇 개인지 궁금해졌다.

참가자 여러분도 궁금하지요?

안 궁금함? 15ㄱ

입력

N이 주어진다. (1 <= N <= 1,515)

출력

문제의 답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

1515

예제 출력

939178250

내가 했던 풀이 방법

dp 배열을 N+1 크기로 초기화하고 각 요소를 15 크기의 배열로 선언하고 0으로 채워준다. 여기서 N+1 크기로 초기화하는 이유는 N자리 수를 위해서이고, 각각 15크기 배열로 선언한 이유는 0부터 14까지의 나머지를 의미한다. 즉 dp[i][j]는 i자리 숫자를 만들었을 때, 숫자를 15로 나눈 나머지가 j인 경우의 수를 의미한다.
dp[0][0]은 0자리 수이고, 나머지가 0인 경우는 1개밖에 없으므로 1로 저장해준다.
1부터 N까지 반복하면서, 현재 자리에서 15로 나눈 나머지가 j인 모든 경우를 for문을 통해 처리해준다. i-1 자리까지 계산했을 때, 나머지가 j인 경우의 수가 존재할 때, 기존 나머지 j에 숫자 1 또는 5를 추가했을 때의 새로운 나머지를 저장해준다. 이를 계산할 때마다 1,000,000,007로 나누어 값이 커지지 않게 한다.
3번을 모두 처리해준 뒤에 dp[N][0]에 N자리 수이면서 나머지가 0인(=15의 배수) 경우를 출력해준다.

코드

var fs = require('fs');
let N = Number(fs.readFileSync(0, 'utf-8').toString().trim());

let dp = Array.from({ length: N + 1 }, () => Array(15).fill(0));
dp[0][0] = 1;

for (let i = 1; i <= N; i++) {
  for (let j = 0; j < 15; j++) {
    if (dp[i - 1][j] > 0) {
      dp[i][(j * 10 + 1) % 15] += dp[i - 1][j];
      dp[i][(j * 10 + 1) % 15] %= 1000000007;

      dp[i][(j * 10 + 5) % 15] += dp[i - 1][j];
      dp[i][(j * 10 + 5) % 15] %= 1000000007;
    }
  }
}

console.log(dp[N][0]);