백준 1904 01타일(dynamic programming)

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

1904번: 01타일

#include <iostream>

using namespace std;

const int MAX = 1000000;
const int MOD = 15746;
int N;
int dp[MAX];

void tiling()
{
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= N; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }
    cout << dp[N];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    tiling();
}

 

실버 3의 난이도로 보기에는 상당히 쉬운 것 같다.

 

A4 용지에 하나하나 적다보면 점화식은 금방 도출된다. 조금 더 dp스럽게 생각해본다면 dp[i]에서 경우의 수는 dp[i-1]에 1을 붙이는 경우, dp[i-2]에 00을 붙이는 경우가 있다.

앞부분 뿐만 아니라 뒷부분에 붙이는 경우도 존재하기 때문에 전체의 2배를 해주어야 하지만 정확히 절반이 중복이다.(다른 블로그를 보니 따라서 N-2에선 맨 뒤에 00만 붙이고, N-1에선 맨 앞에 1만 붙이면 중복 없이 값을 구할 수 있다고 한다.)

 

다시 시작한지 1주일 밖에 안됐는데 내 자신이 너무 조급해하는 것 같다는 느낌이 든다. 조급한 마음은 원동력이 될 수도 장애물이 될 수도 있다. 천천히.... 조금은 마음을 천천히 가질 필요가 있다. 많은 문제를 풀려고 욕심부리지 말고 푼 문제들을 확실히 이해하는데 집중하자.