[BOJ] 11727. 2xn 타일링 2(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

이전 문제와 유사한 문제이다.

마찬가지로 먼저

직관적으로 구할 수 있는 2xn 크기까지 채울 수 있는 방법을 찾아보자.

가로선과 세로선, 2x2네모로 그려보면서 하면 쉽게 방법의 수를 찾을 수 있다.

2x1 : 1 가지

2x2 : 3 가지

2x3 : 5 가지

2x4 : 11 가지

2x5 : 21가지

여기서 바로 점화식을 찾을 수 있어야 한다.

dp[i] = dp[i-1] + dp[i-2] * 2

사실 이전 문제에서 *2 만 더 해주면 된다..ㅋㅋㅋ

마지막으로, 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력해야하므로

dp[i]를 구하는 과정에 나누기 연산을 수행해줘야 한다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include <cstdio>   int main(void) {     int n, i;     int dp[1001] = { 0, 1, 3, };     scanf("%d", &n);       for (i = 3; i <= n; i++) {         dp[i] = dp[i - 1] + dp[i - 2] * 2;         if (dp[i] >= 10007) dp[i] = dp[i] % 10007;     }          printf("%d\n", dp[n]);     return 0; } Colored by Color Scripter

cs

line 10) 마찬가지로 점화식을 잘 찾아서 해결하는게 포인트이다.

#. Other Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

/* reference : subinium */   #include <stdio.h>   int main(void) {     int a=1,b=1;     int n;     int tmp;     int count = 0;     scanf("%d",&n);     while(count!=n){         tmp = a;         a = b;         b = 2*tmp+b;         count++;         if(a>=10007){             a%=10007;         }     }     printf("%d",a); }

cs

* 이번 문제도 마찬가지로 배열을 사용하지 않고 swap을 활용하여 해결하셨다.