백준 1904번 01타일[C++]

1904번 문제는 문제를 보고 규칙이 생각나지 않았습니다. 그래서 DP문제이므로 N값에 대한 결과 값을 나열해보았더니 규칙을 찾았습니다.

DP문제를 푸는 방법 중에 생각이 풀이 방법이 생각이 나지 않는다면 값을 나열하며 결과 값 수열의 규칙을 찾는 것도 좋은 방법인 것 같습니다.

나열을 해보니

N = 1 >> 1 -> 1가지

N = 2 >> 00, 11 -> 2가지

N = 3 >> 100, 001, 111 ->3가지

N = 4 >> 0000, 1100, 1001, 0011, 1111 -> 5가지

N = 5 >> 10000, 00100, 00001, 11100, 11001, 10011, 00111, 11111 -> 8가지

까지 구해봤는데 숫자들이 익숙해서 N = 6인 경우를 구해봤더니 13가지였습니다. 이 패턴은 피보나치의 패턴과 같기도 하였습니다.

따라서

0값이 0

1 값이 1

2 값이 2까지 설정한 후

점화식을 새우면 dp [i] = dp [i-1] + dp [i-2]라는 수식이 만들어졌습니다.

#include <iostream>
#include <vector>
using namespace std;
vector<long long> v;
int main(){
    int n;
    scanf("%d", &n);
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    for(int i = 3; i <= n; i++){
        v.push_back((v[i-1]+v[i-2])%15746);
    }
    printf("%d", v[n]);
    return 0;
}

이문제의 실수 요인으로는 15746으로 나눈 값의 나머지를 출력하라고 해서 마지막 결과 값에 %15746만 추가 연산을 하는 경우가 있을 수 있는데 N값이 충분히 커졌을 때 이미 중간에서 long long의 허용범위를 넘어서는 값이 발생할 수도 있기 때문에 애초에 값을 저장할 때 % 연산을 통해 값을 저장해주었습니다(더해서 나머지를 구하나 나머지끼리 더해서 구하나 연산 값은 같음)