[백준] 11726번 2xn 타일링 ( 파이썬 / c언어 )

│문제

11726번: 2×n 타일링

 

│풀이 (Python)

memo={0:0,1:1,2:2}
def tileFill(n):
    if n in memo:
        return memo[n]
    else:
        memo[n]=tileFill(n-1)+tileFill(n-2)
        return memo[n]


n=int(input())
print(tileFill(n)%10007)

 

│설명  (Python) 

 

2xn 타일링 문제 풀이에 관해 생각의 흐름은 경우의 수이다. 세로로 한개의 타일이 있다고 가정할 때 다음 타일이 올 수 있는 경우의 수는 2개이다. n이 2보다 큰경우 가로 2개 또는 세로 1개를 놓을 수 있고, n이 2보다 작은 경우 가로로 2개를 놓을 수 없다. 

 

 

그림과 같이 2가지의 경우만 존재하므로, 타일을 세로로 1개 두는 경우인 tileFill(n-1) 과 가로로 2개 두는 경우인 tileFill(n-2)를 재귀로 반복적으로 호출하는 구조로 볼 수 있다. 이에 기반하여 기본적인 코드작성은 아래와 같다.

 

def tileFill(n):
    if n<=2:return n
    else:
        return tileFill(n-1)+tileFill(n-2)


n=int(input())
print(tileFill(n)%10007)

 

keypoint 1- 메모이제이션을 사용하지 않으면 시간초과 문제가 발생한다.

dp문제의 근본적인 시간초과 문제를 해결하기 위해서는 반드시 메모이제이션 기법을 사용해야한다.

 

이에 관한 자세한내용은 추후 포스팅하겠다.

 

기본적인 타일링 코드에서 n<=2작을 때 return n 이므로 메모이제이션은 memo={0:0,1:1,2:2} 로 초깃값을 잡고,

memo[n]=tileFill(n-1)+tileFill(n-2) 을 통해 메모이제이션에 없는 값이면 반복적인 재귀호출을 통해 값을 입력한다.

 

 

│풀이 (C언어)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int memo[1001] = {1,1,2};
int tileFill(int n) {
    if (memo[n] != 0) return memo[n];
    else {
        memo[n] = (tileFill(n - 1) + tileFill(n - 2)) % 10007;
        return memo[n];
    }
}


int main(void) {
    int n = 0;
    scanf("%d", &n);
    printf("%d", tileFill(n));
    return 0;
}

 

│설명  (C언어)

문제의 기본 풀이방법에 대해서는 위 python설명을 참고하길 바란다.

 

int memo[1001] = {1,1,2}; 배열의 0번 원소는 의미가 없기에 어떠한 값이 들어가도 상관은 없지만, if (memo[n] != 0) return memo[n]; 메모이제이션에 포함된 값인지 아닌지 판별할 때 0을 사용하므로,

쓰레기 값인 1을 추가하여 풀이하였다.

 

keypoint 1- %10007의 위치

파이썬으로 푼 후 c언어로 다시 풀어봤지만, 똑같이 풀이 시 틀렸었다. 

필자의 경우 첫 풀이시에 memo[n] = (tileFill(n - 1) + tileFill(n - 2)) ;   /  printf("%d", tileFill(n)% 10007);로 풀이 하였다.

하지만 디버깅시 예제에는 문제가 없었지만, n의 값이 커짐에 따라 오차가 발생하였다. 이 문제는 c언어의 특성중 하나인데, int형 범위에 따른 정수의 오차가 발생하며 큰 값의 %계산 값 마저 오차가 발생한다.

 

이런 성격을 띄는 문제 같은 경우 보통 long long자료형을 사용하지만, 11726번 2xn 타일링 문제는 %10007의 위치를 아래코드와 같이 변경만으로 쉽게 해결가능하다. 

 

memo[n] = (tileFill(n - 1) + tileFill(n - 2)) % 10007;     /      printf("%d", tileFill(n));