BaekJoon_1904(01타일)

문제

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

1904번: 01타일

문제풀이

짖궂은 동주 때문에 0을 낱개로 사용할 수 없게 되었다... (1와 00 만 사용가능)

N이 1 일 때부터 경우의 수를 보면 금방 규칙을 파악할 수 있다.

 

N = 1 일 때 , 1 => 1개

N = 2 일 때, 11 / 00 => 2개

N = 3 일 때, 100 / 001 / 111 => 3개

N = 4 일 때, 1111 / 1001 / 0000 / 0011 / 1100 => 5개

N = 5 일 때, 11111 / 00111 / 10011 / 10011 / 11001 / 11100 / 00001 / 00100 => 8개

 

전형적인 피보나치 수열의 형태를 보이고 있다.

점화식을 새워보면

dp(n) = dp(n-1) + dp(n-2)

초기값으로는 

dp[0] = 1

dp[1] = 2 로 설정하면 dp[3]부터 반복문을 통해서 얻을 수 있다.

 

코드

const answer = (number) => {
    const arr = Array.from({length : number + 1}, () => 0);

    arr[1] = 1;
    arr[2] = 2;

    for (let index = 3; index < arr.length; index++) {
        arr[index] = (arr[index-1] + arr[index-2]) % 15746;        
    }

    const result = arr[number];

    console.log(result);
}


const input = [];
require("readline")
    .createInterface(process.stdin, process.stdout)
    .on("line", (line) => {
        input.push(line);
    })
    .on("close", () => {
        // console.log(input)
        answer(Number(input));
        process.exit();
    });

 

코드는 깃헙에서도 확인할 수 있습니다 :)

https://github.com/duduchi/Algorithm/tree/main/Dynamic

GitHub - duduchi/Algorithm: 알고리즘 이론 및 구현 소스 정리 프로젝트 입니다.