Skip to content
logo
Padosum Wiki
Github
On this page

백준 1904 JavaScript

수정하기
문서 생성 2022-04-29 12:27:38 최근 수정 2022-04-29 20:53:15
On this page

문제

백준 1904

풀이

문제를 풀기 위해 나오는 2진 수열을 나열해보자.

// 1, 00 이 적힌 타일
// N=1 => 1
// N=2 => 00, 11
// N=3 => 001, 111, 100
// N=4 => 0011, 0000, 1001, 1100, 1111
// N=5 => 00111, 00001, 10011, 11001, 11111 -> N=4에 1 추가
//        10000, 11100, 00100, 11000    -> N=3에 00추가
// N=6 => 001111, 000011, 100111, 110011, 111111
//        100001, 111001, 001001, 110001   -> N=5에 1 추가
//        001100, 000000, 100100, 110000, 111100 -> N=4에 00추가

위와 같이 나열하면 규칙을 발견할 수 있다. 사용할 수 있는 숫자 타일은 총 2가지 00과 1이므로 두 가지 방법으로 조합할 수 있다.

  • N자리 수열은 N-1자리 수열에 하나의 숫자를 추가해야 하는데 00과 1중 1만 가능하다. 따라서 N-1자리로 만드는 수열들에 1을 추가하면 된다.
  • N자리 수열은 N-2자리 수열에 두자리 숫자를 추가하면 N자리가 되는데 00을 추가하면 된다.

따라서 다음과 같은 결론이 내려진다. 이전에 계산해 놓은 값을 활용할 수 있다. 즉, Dynamic-Programming으로 해결해볼 수 있겠다.

N자리로 이뤄진 2진 수열의 개수 = N-1자리로 이뤄진 2진 수열의 개수 + N-2자리로 이뤄진 2진 수열의 개수

전체코드는 다음과 같다. 주의할 점은 결과값에만 15746로 나머지 연산을 하니 메모리 초과가 났다. 이유는 최대값인 1,00,000을 넣어보니 알 수 있었다. 숫자가 너무 커서 였다. 그래서 DP배열의 값을 구할 때마다 15746으로 나눴다.

const readFileSyncPath = require('path')
  .basename(__filename)
  .replace(/js$/, 'txt')


// const readFileSyncPath = '/dev/stdin';


const input = require('fs')
  .readFileSync(readFileSyncPath)
  .toString()
  .trim()
  .split('\n')


// 1, 00 이 적힌 타일
// N=1 => 1
// N=2 => 00, 11
// N=3 => 001, 111, 100
// N=4 => 0011, 0000, 1001, 1100, 1111
// N=5 => 00111, 00001, 10011, 11001, 11111 -> N=4에 1 추가
//        10000, 11100, 00100, 11000    -> N=3에 00추가
// N=6 => 001111, 000011, 100111, 110011, 111111
//        100001, 111001, 001001, 110001   -> N=5에 1 추가
//        001100, 000000, 100100, 110000, 111100 -> N=4에 00추가


// N자리로 이뤄진 2진 수열의 개수 = N-1자리로 이뤄진 2진 수열의 개수 + N-2자리로 이뤄진 2진 수열의 개수


const N = Number(input[0])
const DP = Array.from({ length: N + 1 }).fill(0)
DP[1] = 1
DP[2] = 2


for (let i = 3; i <= N; i++) {
  DP[i] = (DP[i - 2] + DP[i - 1]) % 15746
}
console.log(DP[N])

LINKS TO THIS PAGE