1904번 : 01타일

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

1904번: 01타일

 

 

오랜만에 깔끔하게 풀은 문제!

 

 

---

 

 

 

DP문제로 분류되어 있어서, DP로 접근하긴 했다. 

 

 

 

 

이 문제는 비교적 쉬운 DP문제라 노골적으로 DP문제임을 보여주고 있다. N = 1일 때, N = 2일 때 등을 보여주면서, 점화식 관계를 찾아야 한다고 힌트를 주고 있다.

 

 

 

 

N = 3일 경우에 어떻게 만들어지는걸까?

 

 

 

 

N[3]이 만들어질 수 있는 방법은 다음과 같다.

 

 

 

 

N[2] + '1'

N[1] + '00'

 

 

 

 

두 가지 방법의 합으로 생각하면 될 것이다.

 

 

 

 

누군가는 N[1] + '11'도 들어가야 하지 않을까라고 착각할 수 있지만,

 

 

 

 

N[1] + '11'은, N[2] +'1'에 포함되므로, 중복해서 갯수를 새는 것이므로 제외시켜야 한다. 겹치지 않게 N[3]을 구하는 것이 중요하다.

 

 

 

 

이 관계를 점화식으로 표현해보면,

 

 

 

 

N[3] = (N[2] * 1)+ (N[1] * 1)인데, 일반화해보면,

 

 

 

 

N[i] = N[i - 1] + N[i - 2] (i >=3)

 

 

 

 

각 값을, 15746으로 나눈 나머지를 구해야 하므로 적절하게 변환이 필요하다.

 

 

 

 

N[i] = (N[i - 1] % 15746 + N[i - 2] % 15746) % 15746;

 

 

 

 

으로 계산하면 된다.

 

 

 

 

---

 

 

해설코드(C++).

 

 

 

#include <iostream>
 
using namespace std;
 
int N;
 
int main(void) {
    cin >> N;
    int dp[1000001] = { 0 };
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= N; i++)
        dp[i] = ((dp[i - 2] % 15746) + (dp[i - 1] % 15746)) % 15746;
    cout << dp[N] << endl;
    return 0;
}