[백준] 11726번: 2xn 타일링

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

문제

알고리즘 접근 방법

DP로 bottom-up 방식을 활용한다.

N번째 블록의 개수 = N-1개 블록에서 | 모양을 더한 것 + N-2개 블록에서 = 모양을 더한 것

고로 dp[N] = dp[N-1] + dp[N-2] 이다.

반복문을 다 돌고 100007로 나누면 수가 매우 커지기 때문에 dp[i]를 구할 때마다 100007로 나눈 나머지를 구해준다.

풀이

#include <iostream>

using namespace std;

int main(){
    int n;

    cin >> n;

    int dp[n+1] = {0, };

    dp[1] = 1;
    dp[2] = 2;

    for(int i=3; i<=n; i++){
        dp[i] += (dp[i-1] + dp[i-2]) % 10007;
    }

    cout << dp[n] << endl;
    return 0;
}

정리

가로로 놨을 때 (=) 의 경우를 생각하지 못했다. 까비

💡 참고 포스팅

mountrivers님 블로그
SWKo님 블로그