백준, BOJ, 1904번 C++ [CPP]

DP문제다.

하지만 역시 문제를 생각하는데 오래걸렸다. 20분쯤 걸린듯..ㅠ

시간제한보면.. 무조건 DP란 것이 느껴진다.

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

 

---

 

#맞는 풀이

#include<iostream>
#define X 15746
using namespace std;

long long dp[1000001];
int N;

int main(){
    cin >> N;
    
    // 맨 끝의 타일이 00으로 끝나느냐 1로 끝나느냐의 차이를 생각해보자
    dp[1] = 1;
    dp[2] = 2;
    //숫자가 너무 커지기 때문에.. 답이 제대로 나오지 않음
    for(int i = 3; i<=N; i++){
        dp[i] = (dp[i-2]+dp[i-1])%X;
    }
    
    cout << dp[N];
}

 

 

처음에 쉬웠다. 그리고 결과를 위해선

숫자가 엄청 커지기 때문에

%을 이용해야 한다.

 

우선 %도 몇가지 법칙이 있다.

A = B + C라고 하자

A%N = (B%N + C%N)%N

A를 직접 나누기보다 B와 C를 나누어서 더한 다음 다시 나누는 것으로 크기를 줄여서 나머지를 구할 수 있다.

참고하고

 

DP문제의 핵심은 이전 결과를 어떻게 이용할까다..

그래서 맨 끝에 타일은 무엇이 올 수 있을까?? 생각해보면 답이 나온다.

1로 끝나거나 00으로 끝난다.

 

즉, 1로 끝나는 것들은 앞서 나온 타일(N-1)들의 조합에 1만 붙인 것이고

00으로 끝나는 것들은  앞서 나온 타일(N-2)들의 조합이 00만 붙인 것이다.