타일 DP 문제

1904

문제

알면 쉽지만 모르면 못푸는 dp문제다.

패드산지가 반년인데 필기어플을 아직도 안샀다

그림을 보면서 이해하면 편한데
1일때는 1타일 하나만 들어가서 dp[1] = 1
2일때는 11, 00 두개가 가능해서 dp[2]이다.

3일때는 어떨까?
우선 00타일을 고정으로 놓자. 남은 자리는 한칸이다 이 한칸은 1한개만 올 수 있다.

dp[3] = dp[1]

그 다음에는 1을 고정으로 놓자. 그러면 2칸이 남는다. 이 두칸은 00 11 2개가 올 수 있고 이는 미리 구해둔 dp[2]이다.

따라서
dp[3] = dp[1] + dp[2]이다.

여기서 dp[n] = dp[n-1] + dp[n-2]라고 할 수도 있겠지만,
한번 더 해보자.

4일때는 다음과 같다.
1. 00타일 고정
2. 두칸이 남는다.
3. dp[2]

1. 1타일 고정
2. 세칸이 남는다.
3. dp[3]

따라서 dp[4] = dp[2] + dp[3]이고 dp[n] = dp[n-1] + dp[n-2]이다.

코드로 구현

#include <iostream>
using namespace std;
#define max 1000000

int dp[max];
int n;

int main() {
    cin >> n;

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

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

문제의 조건에 15746으로 나누라는 조건이 있는데 처음에 답에다가만 나눴다가 틀렸다.

n이 백만까지 가서 범위오류가나기 때문이다.
따라서 각 dp에 미리미리 나눠주도록하자.

9461

문제)

이전문제보다는 쉽다.

하나씩 그려가다보면 규칙이 보인다.

dp[i] = dp[i-1] + dp[i-5]이다.
따라서 규칙은 6부터 생긴다.

코드

#include <iostream>
using namespace std;

long t, n;
long dp[100];

int main() {
    cin >> t;
    for (int i = 0; i <= 6; i++) {
        if (i < 4) dp[i] = 1;
        else if (i == 4 || i == 5) dp[i] = 2;
        else dp[6] = 3;
    }
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int i = 7; i <= n; i++) {
            dp[i] = dp[i-5] + dp[i-1];
        }
        cout << dp[n]<< "\n";
    }
}

아마 틀린 사람들의 대부분은 int형으로 써서 틀렸을것이다.
수가 커서 long형으로 써야 오류가 없다.