2024/12/30 화 매일백준

오늘의 문제는

11727번: 2xn 타일링 2

입니다.

문제는 위와 같습니다. 그 제가 올린 블로그 글 중 이와 비슷한 문제가 있었던 걸로 기억해요
색칠하는 건가 여튼

그래서 쉽게 접근할 수 있었던 것 같습니다.

이전까지의 경우에 새롭게 만들어질 수 있는 조합을 생각하면 위와 같습니다.
순서가 바뀌는 경우는 이미 이전의 경우에 다 포함되어있기 때문에 어떤 모양이 들어올 수 있는지에 대해서만 체크하면 된다.

따라서 점화식은

입니다.

코드는

#include <iostream>

using namespace std;

int main(void) {

    int n;
    unsigned long long DP[1001] = {0};

    cin >> n;

    DP[1] = 1, DP[2] = 3;

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

    cout << DP[n] << endl;

    return 0;
}

이다. 처음에 통과과 되지 않아서 왜지 하면서 dp를 저렇게 수정하게 되었습니다.

틀렸던 이유는 나머지 값을 출력하라는 문제인데 나머지 연산을 하지 않았더라구요.
모듈 연산의 특징을 이용하면 중간에 모듈연산을 진행해도 상관없으므로 저렇게 표현하였습니다.

끝.
그리고 이제 슬슬 알바도 해야되서 아마 제 날짜에 글을 쓰는게 어려울 수도 있다.
출간 날짜는 틀리더라도 제목에 맞춰서 글을 쓰도록 하겠습니다.
진짜 끝.