[python/파이썬] 백준 11726 2xn 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

 

 

[문제 풀이]

 

이 문제는 언뜻보면 굉장히 복잡해 보이지만, 조금만 생각하면 간단한 문제이다.

직사각형과 타일 모두 세로의 길이가 고정되어 있으므로 가로의 길이만 생각하면 된다.

 

2xn으로 생각하지 않고 그냥 n이라는 수를 1 혹은 2를 더해서 만들어주는 문제와 동일하다.

dp로 간단하게 풀 수 있는 문제이다.

 

문제에서 제시하는 그림을 다시 보면

이 사각형을 세로로 반을 자른다고 해도 이 문제의 본질이 바뀌지는 않는다.

 

그렇게 되면 1x1 정사각형과, 1x2의 직사각형으로 1xn의 직사각형을 채우는 문제가 된다.

 

n의 범위는 1이상 1,000 이하 이므로 

1부터 살펴보면

n=1 

1가지 : 1

n=2

2가지 : 1 1 / 2

 

이 두가지 경우를 초깃값으로 설정하고

그 이후부터는 n-1의 가짓수와 n-2의 가짓수를 더해서 n의 가짓수를 구할 수 있다.

 

n=3

3가지

( 1 ) 2 #n=1

( 1 1 ) 1 #n=2

( 2 ) 1 #n=2

 

n=4 

5가지

( 1 1 ) 2  #n=2

( 2 ) 2 #n=2

( 1 2 ) 1 #n=3

( 1 1 1 ) 1 #n=3

( 2 1 ) 1 #n=3

 

즉 dp[n] = dp[n-1] + dp[n-2]가 된다.

 

 

[소스 코드]

"첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다."

출력을 꼭 유의하여 코드를 작성해야 틀리지 않는다.

처음에 10,007로 나눈 나머지를 출력해야 한다는 내용을 못 보고 그냥 제출했더니 틀렸다고 나왔다.

 

n = int(input())

dp = [0,1,2]

for i in range(3,n+1):
    dp.append(dp[i-1]+dp[i-2])
    
print(dp[n]%10007) #출력 주의! 꼭 10007로 나눈 나머지가 출력되도록 할것