백준 11726 파이썬 | 2xn 타일링

코드

from sys import stdin
input = stdin.readline

n = int(input())
dp = [0, 1, 2]
for i in range(3, n+1):
    dp.append(dp[i-2] + dp[i-1])

print(dp[n]%10007)

설명

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하면 된다.

문제를 봤을 때 수학 문제를 풀 때 처럼 경우의 수를 이용하여 풀 수도 있을거라는 생각이 들었다. 하지만 알고리즘 문제이기 때문에 알고리즘을 풀 듯이 풀어야한다. 여러 문제를 풀며 느낀건데, 간단한 공식을 알고 있어서 그걸 알고리즘에 적용하는 것은 괜찮아도 완전히 알고리즘 문제를 수학 문제 풀듯이 접근하는 것은 좋지 않은 것 같다.

아무튼 알고리즘을 풀듯이 접근 해 보면 일단 n의 크기가 1부터 하나씩 커지니 n = 1, 2, 3 ... 일 때 출력이 어떻게 되는지 알아보았다.

n = 1 -> 1

n = 2 -> 2

n = 3 -> 3

n = 4 -> 5

이런 결과가 나온다. 여기까지 해보면 이 수열은 피보나치 수열이 아닐까 하는 강한 의심이 든다. 실제로 n = 5 일 때도 직접 그려보면 결과는 8이 된다. 하지만 n의 숫자가 커질 수록 경우의 수를 하나하나 세기가 귀찮기 때문에 규칙이 있는 것 같으면 일단 만들어 보고 예제 출력과 비교해 보거나 제출 하고 결과를 봐 보는 것이 낫다.

피보나치 수열을 동적프로그래밍을 이용하여 구현 할 때와 동일한 방법으로 알고리즘을 구현하면 된다. 그리고 10,007로 나눈 나머지를 출력하라고 했으므로 마지막에 나머지 연산을 추가해야 한다. 나는 마지막에 나머지 연산을 안 해서 한 번 틀렸다 ㅋㅋ.

 

메모리: 29200 KB

시간: 80 ms

문제

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

11726번: 2×n 타일링