백준 - 11726번 2×n 타일링 python 문제풀이 [Hellfer]

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

11726번: 2×n 타일링

🔷 알고리즘 분류 - 다이내믹프로그래밍, 난이도 - 실버 5

🔶 문제 이해하기 

2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 문제입니다. 여기서 1x2 타일은 가로로 두 칸, 세로로 한 칸을 차지하고, 2x1 타일은 세로로 두 칸, 가로로 한 칸을 차지합니다. 

 

즉, 가로로 두 칸을 차지하는 타일을 세로로 놓거나, 세로로 두 칸을 차지하는 타일을 가로로 놓는 경우를 고려해야 합니다.

이 문제의 핵심은 "타일을 놓는 방법의 수"를 찾는 것입니다. 여기서 주의해야 할 점은, 모든 가능한 방법을 고려해야 

하며, 이를 효율적으로 계산할 수 있는 방법을 찾아내는 것입니다.

이 문제를 해결하기 위한 힌트 중 하나는 "동적 프로그래밍"입니다. 동적 프로그래밍은 복잡한 문제를 간단한 여러 

개의 문제로 나누어 푸는 방법으로, 이 문제에서는 2xN 크기의 직사각형을 2x1 크기의 작은 직사각형으로 나누어 각각을 채우는 방법의 수를 찾고, 이를 합치는 방식으로 문제를 해결할 수 있습니다.

2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 문제에서 타일을 놓는 방법은 다음과 같습니다.

N=1인 경우: 1x2 타일 1개를 세로로 놓는 1가지 방법이 있습니다.

N=2인 경우: 1x2 타일 2개를 가로로 놓거나, 2x1 타일 2개를 세로로 놓는 2가지 방법이 있습니다.

N이 3 이상인 경우, N-1까지 채우고 2x1 타일을 추가하는 방법과 N-2까지 채우고 1x2 타일 2개를 추가하는 방법을 

합치면 N을 채우는 방법의 수를 구할 수 있습니다.

예를 들어, N=3인 경우 다음과 같은 3가지 방법이 있습니다.

1. 2x1 타일을 세로로 3개 놓는 방법

2. 1x2 타일을 가로로 2개와 2x1 타일을 세로로 1개 놓는 방법

3. 2x1 타일을 세로로 1개와 1x2 타일을 가로로 2개 놓는 방법

이렇게 놓는 방법의 수를 계산하면, N=1일 때 1가지, N=2일 때 2가지, N=3일 때 3가지, N=4일 때 5가지, N=5일 때 8가지, N=6일 때 13가지와 같이 피보나치 수열이 나오게 됩니다. 따라서 N을 채우는 방법의 수는 피보나치수열의 N+1번째 항과 같습니다.

🔶문제풀이 - 다이내믹프로그래밍을 이용한 풀이

# 입력받은 수를 n에 저장합니다.
n = int(input())

# 동적 프로그래밍을 위한 리스트 dp를 생성합니다. 초기값은 0, 1, 2 입니다.
# dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수를 저장합니다.
dp = [0, 1, 2]

# 3부터 n까지 반복합니다.
for i in range(3, n+1):
    # dp[i]는 dp[i-1]과 dp[i-2]의 합이 됩니다.
    # 즉, i-1까지 채우고 2x1 타일을 추가하는 방법과 i-2까지 채우고 1x2 타일을 추가하는 방법을 합칩니다.
    # 이 값을 10007로 나눈 나머지를 dp 리스트에 추가합니다.
    dp.append((dp[i-1] + dp[i-2]) % 10007)

# 2xn 크기의 직사각형을 채우는 방법의 수를 10007로 나눈 나머지를 출력합니다.
print(dp[n])

🔶 문제 해결전략

이 문제를 쉽게 생각하는 방법 중 하나는 "마지막 타일을 어떻게 놓았는가"를 생각하는 것입니다.

2xN 크기의 직사각형을 채우려면, 마지막에 2x1 타일을 세로로 놓는 경우와 1x2 타일을 가로로 두 개 놓는 경우를 생각할 수 있습니다.

만약 마지막에 2x1 타일을 세로로 놓았다면, 나머지는 2x(N-1) 크기의 직사각형을 채우는 방법의 수와 같습니다.
만약 마지막에 1x2 타일을 가로로 두 개 놓았다면, 나머지는 2x(N-2) 크기의 직사각형을 채우는 방법의 수와 같습니다.

따라서, 2xN 크기의 직사각형을 채우는 방법의 수는 2x(N-1) 크기의 직사각형을 채우는 방법의 수와 2x(N-2) 크기의 직사각형을 채우는 방법의 수를 합친 것과 같습니다.

이는 피보나치수열과 동일한 원리입니다. 피보나치수열에서 각 항은 바로 앞의 두 항의 합으로 표현됩니다. 이와 마찬가지로, 이 문제에서 각 N에 대한 타일 놓는 방법의 수는 N-1과 N-2에 대한 타일 놓는 방법의 수를 합한 것과 같습니다.

 

🤗파이팅입니다~ 여러분!!🤗