[파이썬 11726번] 2 x n 타일링

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

11726번: 2×n 타일링

 

 

 

# 조건

• 2xN 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램 작성
• 방법의 수를 10,007로 나눈 나머지를 출력하라.

 

# 접근 방법

• 규칙을 찾는 것이 좋을 것 같다.
• n = 1 인 경우 1가지
• n = 2 인 경우 2가지
• n = 3 인 경우 3가지
• n = 4 인 경우 5가지
• n = 5 인 경우 8가지
• f(n) = f(n-2) * 2 + f(n-3) 으로 구할 수 있다.
• 또는 f(n) = f(n-1) + f(n-2)

 

# 내 풀이

N = int(input())  
# 2 x n 의 3번째까지 결과 저장해놓기  
result = [0, 1, 2, 3]  
  
n = 0  
while n <= N:  
    if n<=3:  
        n+=1  
    else:  
        a = result[n-2]*2 + result[n-3]  
        result.append(a)  
        n+=1  
print(result[N]%10007)

 

 

# 다른 사람 풀이

a=b=1
exec('a,b=b,a+b;'*int(input()))
print(a%10007)

• exec 함수는 eval과 조금 다르게 문자로 된 '구문'을 인수로 받아 파이썬 컴파일 코드로 변환해준다.

참고 - https://nan491.tistory.com/entry/Python-3-eval-%ED%95%A8%EC%88%98%EC%99%80-exec-%ED%95%A8%EC%88%98