[Python] 백준 11726번_2xn 타일링

문제 

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

11726번: 2×n 타일링

 

코드

def factorial(k):
    total = 1
    for i in range(2,k+1):
        total *= i
    return total

result = [1] #인덱스 0 (=2*1타일이 0개인 경우)의 경우의 수는 무조건 1
num = int(input())
for i in range(1, (num//2)+1):
    v = factorial(num-i)//(factorial(i)*factorial(num-2*i))
    result.append(v)
print(sum(result)%10007)

개선 ver

num = int(input())
way = [0]*(num+1)
#way[1], way[2] = 1, 2

for i in range(1, num+1): #입력값이 1일때 index error를 방지하기 위해 for문 안에서 함께 처리
    if i == 1:
        way[i] = 1
    elif i == 2:
        way[i] = 2
    else:
        way[i] = way[i-1] + way[i-2]
print(way[num]%10007)

풀이 

• 첫 번째 풀이 방식은 전혀 DP를 고려하지 않았다고 봐도 무방하다^^... 자세한 설명은 생략...
  • 팩토리얼 함수를 별도로 정의해서 사용했다.
  • 1*2 블럭은 1개만 사용하지 못하고, 무조건 2개씩 묶어서 사용해야 하므로 사실상 2*2 블럭으로 취급했다.
  • 리스트를 사용해 값을 누적하긴 했지만 그냥 2*n 경우의 수만 계산하기 위한 중간값 저장용이다...
  • 이렇게 풀이한 결과 시간이 엄청나게 많이 소요됐다.. 최악!
• 두 번째 풀이방식은 정답 코드들을 참고해 새로운 접근법을 익혀보았다. 
  • 자세한 설명은 아래에 나와있다.
  • 이번엔 경우의 수를 담을 배열을 먼저 생성해주었다.
  • 가로길이가 1, 2일때 값을 각각먼저 배정해주고 싶었는데, 그러면 입력값이 1인경우 index error가 발생
  • 따라서 배열을 생성만 하되, 값 할당은 for문 안에서 if-elif 문으로 처리해줬다.

다른 풀이 

 출처: https://www.acmicpc.net/source/17737134

num = int(input())
a = [0]*(num+1)

for i in range(1,num+1):
    if i == 1:
        a[i] = 1
    elif i == 2:
        a[i] = 2 
    else:
        a[i] = a[i-1] + a[i-2]
    
print(a[num]%10007)

• 핵심: a[ i ] = a[ i - 1 ] + a[ i - 2 ]

• 마찬가지로 결과값이 저장될 리스트를 먼저 생성해주었다. 0까지 카운팅 되므로 길이는 num+1.
• 2*1 면적인 경우 (=a[1]) → 경우의 수가 1개 (2*1 1개)
• 2*2 면적인 경우 (=a[2]) → 경우의 수가 2개 (2*1 2개 / 1*2 2개)
• 나머지 경우에는 피보나치 수열과 동일하게 해당 인덱스 전 2개의 값의 합으로 그 값이 누적되는 방식이다

• 식을 도출하기 위해 그림을 그려보았다. 2*4 면적의 경우 가능한 경우의 수는 5이다. 
  
  • 크게 2 분류 가능한데, 2*1블럭이 한쪽에 고정된 경우 / 2*2블럭(한 세트니까)이 한쪽에 고정된 경우 이렇게이다.
    • 자세히 설명하자면, 가로가 4라는 것은 3+1일수도 있고, 2+2일수도 있다. 이렇게 선정한 이유는 +1일때 2*1블록을 이용할 것이고, +2일때는 2*1(2개)를 이용할 것이기 때문이다. 즉, 가지고 있는 최소 블럭단위 2가지를 모두 사용할 수 있는 경우의 수라는 것.
  • 2*1블럭이 1개 고정된 경우는 사실상 고정 블록 제외 3개 블럭의 배치 문제(=4-1)이므로 n=3인경우의 경우의 수와 동일
  • 1*2블럭이 2개 고정된 경우는 사실상 고정 블록 제외 2개 블럭의 배치 문제(=4-2)이므로 n=2인경우의 경우의 수와 동일
  • 따라서 두 경우의 수를 합해주면 n=4일때 경우의 수 값이 도출 가능하다. 
• DP 문제를 풀 땐, 초반의 경우의 수를 구해보고 점화식을 고민해보는 것이 좋을 것 같다.