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

#. Problem

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

* 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 크기까지 채울 수 있는 방법을 찾아보자.

가로선과 세로선으로 그려보면서 하면 쉽게 방법의 수를 찾을 수 있다.

2x1 : 1 가지

2x2 : 2 가지

2x3 : 3 가지

2x4 : 5 가지

2x5 : 8 가지

여기서 바로 점화식이 나온다.

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

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

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

이거 안 나누고 왜 계속 틀렸다고 나오는지 살짝쿵 헤맸다는...

#. Code

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

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

cs

line 9) 점화식만 찾으면 쉽게 풀리는 간단한 문제였다.

#. 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 24

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

cs

* 배열을 사용하지 않고 해결해서 메모리 사용이 굉장이 효율적이다.

line 14~22) cnt가 n과 같을 때까지 반복

line 13~17) a, b의 swap 방법을 활용하여 dp[i] = dp[i-1] + dp[i-2] 점화식을 구현하였다... 

line 19~20) 여기서도 10007까지는 나머지 연산을 사용하지 않아서 속도 측면에서 효율적일 수 있을 것 같다.