[알고리즘_PS] DP주간01 - boj 11727 2*n 타일링 2 by Cpp

문제

---

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

 

코드

---

#include <iostream>
#include <vector>
using namespace std;

int dp[1002] = {
    0,
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 3;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
    }

    cout << dp[n];

    return 0;
}

풀이

---

본 문제 풀이

2*1, 2*2를 만들 수 있는 경우의 수는 위와 같다.

2*3, 2*4 부터 조금 복잡해진다.

2*3은 위와 같다. 2*1에다가 2*2를 붙이기 또는 2*2에다 2*1을 붙이기다. 여기서 주의할 점은 2*1로만 만들어진 2*3블록이 하나 중복된다는 것이다.

2*4는 2*3에 2*1을 추가하거나, 2*2에 2*2를 추가한다. 여기서도 2*1블록이 추가되는 부분에 있어서는 중복이 되는 경우가 있어 주의해야한다.

앞선 경우의 수를 살펴보며 아래와 같은 점화식을 생각할 수 있다.

앞선 예시에서 보듯이 2*n-2의 블록에 2*2의 블록을 붙일 때, 2*1 블록을 붙이는 것은 2*n-1블록에 2*1블록을 붙이는 것과 필연적으로 중복이 될 수 밖에 없다. 따라서 2*2 블록을 붙이는 경우의 수는 2가 된다.

 

 

int범위

10007로 나눈 나머지를 출력 → int 범위 초과하니까 longlongint쓰자 ! 였는데..

생각해보면 나머지를 구하는 거니까 굳이 원본값을 넣을 필요가 없고 그냥 나머지 값만 넣어도 충분했다. 그리고 이렇게 안하면 오답처리남

앞으로도 범위 초과하는 문제같은거면 아예 값을 압축?하는 방안이 없는지 확인해보기