백준 11726 2×n 타일링 c++ [컴공과고씨]

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

11726번: 2×n 타일링

직접 도형을 그려보면서 어떤 규칙이 있는지 보았지만 도형 모양안에서 규칙을 찾기는 힘들었다.

그래서 고민하다가 도형 개수에 대한 규칙을 찾아서 풀었다.

 

도형의 개수

1 -> 1개

2 -> 2개

3 -> 3개

4 -> 5개

5 -> 8개

6 -> 13개

직접 그려보면 이렇게 개수가 나온다.

그럼 점화식이 보인다.  n = (n-1) + (n-2)

근데 중요한 것은 문제에 보면 10007로 나눈 나머지를 구하는 것이다.

해보진 않았지만 답을 다 구한 후 나머지를 구하면 아마 숫자가 커져서 오류가 날 것이다.

그래서 나머지 공식을 이용해주면 된다.

나머지 공식은 (A+B)%N = (A%N + B%N)%N 

그렇기 때문에  

이 부분에서 10007로 나눈 값을 다음에 저장해도 나누지 않은 값을 나눈것과 나머지 값은 같기 때문에 dp에 저장할때 나눈값으로 저장해줘도 되는것이다. 

 

전체코드

#include <iostream>
using namespace std;
int main(){
    int n;
    int dp[1002];
    dp[1] = 1;
    dp[2] = 2;
    cin >> n;
    for (int i = 3; i <= n;i++){ // 점화식
        dp[i] = (dp[i - 1] + dp[i - 2])%10007; // 나머지 공식
    }
    cout << dp[n];
    return 0;
} //38min

체감난이도	걸린시간	참고	사용 알고리즘
중하	38min	x	다이나믹 프로그래밍 (dynamic programming)