[백준] 11726번 2 X n 타일링 (python,c++)

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

11726번: 2×n 타일링

 n개의 숫자로 순열을 만든다했을때,하나의 숫자의 자리가 정해졌다면 나머지 숫자들로 만들 수 있는 경우의 수는 (n-1)!이다.

해당 문제는 이러한 원리와 dp를 이용한다.  먼저 n이 1일때,2일때...를 차례로 그려보며 규칙을 찾는다.

끝블록은 두 블록중 하나인것을 알 수 있다.

이렇게 한 자리가 정해져 있다면, 경우의 수가(n-1)! 과 같은 순열과 같이, 끝 블록이 정해져있을때 경우의수는 이전배열 dp[n-1] 경우의 수와 같다.

 

2 x N 크기의 직사각형을 채울 수 있는 방법의 수 =  2 x (N - 2) 크기의 직사각형을 채울 수 있는 방법의 수 + 2 x (N - 1)크기의 직사각형을 채울 수 있는 방법의 수 

 

(%100007조건은 숫자가 너무 커지는 경우에 답을 간단하게 도출하기 위한 것이니 크게 신경쓸 필요 없다.)

 

---

SOLUTION CODE

# PYTHON

- Bottom up 방식. 시간복잡도 O(N)

 

1) 반복문 풀이

MOD = 10_007
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
n = int(input())
for i in range(3,1001):
    dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[n])

 

2) 재귀 풀이

import sys
sys.setrecursionlimit(10000000)

def calc(n):
    if n==1: return 1
    if n==2: return 2
    if dp[n]==0:
        dp[n] = calc(n-2) + calc(n-1)
    return dp[n]

n = int(input())
dp = [0]* (n+1)
print(calc(n)%10007)

---

# C++

 

1) 반복문 풀이

#include <stdio.h>

int dp[1005] = {1,1};

int main(){
    int n;
    scanf("%d",&n);
    
    for(int i=2;i<=n;i++){
        dp[i] = (dp[i-1]+dp[i-2])%10007;
    }
    
    printf("%d\n",dp[n]);
    return 0;
}

 

2) 재귀 풀이

#include <iostream>
using namespace std;

int dp[1001];

int func(int x){
    if(x==1) return dp[x]=1;
    if(x==2) return dp[x]=2;
    if(dp[x]!=0) return dp[x];
    return dp[x] = (func(x-1)+func(x-2))%10007;
}

int main(){
    int n;
    cin >> n;
    
    cout << func(n);
    return 0;
}