75. Python 백준 11726 번 2Xn 타일링 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 문제인 백준 11726 번 2Xn 타일링 입니다.

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

11726번: 2×n 타일링

 

백준 11726 Python 정답 코드 입니다.

n = int(input())
tile = [0, 1, 2]
while len(tile) <= n:
    tile.append((tile[len(tile) - 1] + tile[len(tile) - 2]) % 10007)
print(tile[n])

 

먼저 타일을 2*n개의 직사각형에 배치하는 방법은 두 가지가 있습니다.

1) 1*2 타일을 넣는다

2) 2*2 타일을 넣는다.

왜 2*1 이 아닌 2*2 tile인지 궁금하실 텐데

어차피 2*1 타일을 위에 넣으면 아래에는 자동적으로 2*1 타일을 넣어야만 하기에

2*2타일이라고 생각해도 논리적으로 같습니다.

 

이제 2*n의 직사각형에 타일을 넣어봅시다.

 2*2의 직사각형에는 두 가지 방법이 있습니다.

1. 1*2 타일을 맨 뒤에 넣는다. | |

2. 2*2 타일을 맨 뒤에 넣는다. =

 

 2*3의 직사각형은 

2*3 직사각형에 맨 뒤에 2*1 타일이 들어가면

자연스럽게 남는 공간은 2*2 이 되므로  Base Case 2*2의 타일링 경우의 수를 더해주고 (n-1) 이미 저장되어 있음

 

2*3 직사각형에 맨 뒤에 2*2 타일이 들어가면

자연스럽게 남는 공간은 2*1 이 되므로 Base Case 2*1 의 타일링 경우의 수를  더해주면 (n-2) 이미 저장되어 있음

2*3직사각형의 타일링 경우의 수가 완성이 됩니다.

 

2*4의 직사각형은

2*4 직사각형에 맨 뒤에 2*1 타일이 들어가면

자연스럽게 남는 공간은 2*3 이 되므로  앞서 구한 2*3의 타일링 경우의 수를 더해주고 (n-1) 방금 구함

 

2*4 직사각형에 맨 뒤에 2*2 타일이 들어가면

자연스럽게 남는 공간은 2*2 이 되므로 Base Case 2*2 의 타일링 경우의 수를  더해주면 (n-2) 이미 저장되어 있음

 

즉 사전에 구한 (n-1) + (n-2) 의 타일링 경우의 수가 n 번째 타일링 경우의 수가 됩니다.

 

결국

(n-1) + (n-2) 을 더해서 n번을 구하는 코드입니다.

리스트인 tile 안에 0, 1, 2번은 Base Case로 넣었고

 

입력 값이 리스트 안에 있는지 검사한 후

만약 없다면

len(tile) <= n

 

없는 부분을 계산해서 문제에서 요구한 저장 방식인 10007로 나눈 나머지 값을 넣어주었습니다.

tile.append((tile[len(tile) - 1] + tile[len(tile) - 2]) % 10007)

 

그리고 n번째 값을 출력하면 됩니다.

print(tile[n])

 

백준 11726 Python 최종 코드 입니다.

n = int(input())
tile = [0, 1, 2, 3, 5, 8 ]
while len(tile) <= n:
    tile.append((tile[len(tile) - 1] + tile[len(tile) - 2]) % 10007)
print(tile[n])

 

파이썬 백준 11726 자세한 설명과 함께 정답 코드이었습니다.

 

감사합니다.