백준 1904 01 타일 / C++

문제 : 1904

풀이 point

패턴을 찾아보면 쉽게 풀수 있다.
제한사항은 0이 짝수개이어야하며 붙어있어야한다는 것이다.

N = 1 : 1
N = 2 : 11 10(x) 01(x) 00
N = 3 : 111 110(x) 101(x) 011(x) 100 001 010(x) 000(x)

N = 4 까지 모든 경우의 수를 구한 후 되는 것과 안되는 것의 차이점을 구해보면 규칙을 찾을 수 있다.

풀이 방법

전에 구한 되는 경우 + 전에 구한 안되는 경우에서 0을 붙이면 된다.

전에 구한 되는 경우에서 1을 붙이면 된다.
전에 구한 안되는 경우에서 0을 붙이면 된다.

전에 구한 안되는 경우는 곧 전전에서 되는 경우와 같다.

점화식으로 나타내보면 dp[i] = dp[i-1] + dp[i-2]

값을 15746으로 나누어주면서 나머지만 취한다.

코드

//백준 1904, 01타일

#include <iostream>

int dp[1'000'001];

int main (){

    int N;
    std::cin >> N;
    dp[1] = 1; dp[2] = 2;
    for(int i{3}; i<=N; ++i){
        dp[i] = dp[i-1]%15746 + dp[i-2]%15746;
    }

    std::cout << dp[N]%15746 << '\n';

    return 0;
}

2025-02-03T04:54:41.846Z