관리 메뉴

코딩 기록 저장소

[백준/Python] 11726번 : 2×n 타일링 본문

백준/기타

[백준/Python] 11726번 : 2×n 타일링

KimNang 2023. 7. 11. 11:24

문제 정보

제목 : 2×n 타일링

번호 : 11726번

사용 언어 : Python

문제 링크

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

 

시간 제한 메모리 제한
1 초 256 MB

 

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

입출력 예제


나의 풀이

input_n이라는 변수를 선언하여 n을 입력받습니다. 만약 n이 1이나 2면 그 값을 그대로 출력합니다. 아니라면 dp 리스트를 생성하여 1과 2에 초기값을 설정하고 for루프를 이용해 n+1까지의 값을 구합니다. for루프가 끝나면 dp[input_n]을 10,007로 나눈 값을 출력합니다.

 

코드

input_n = int(input()) # n 입력받기

if ( input_n == 1) :
    print("1")
elif (input_n == 2) :
    print("2")
else :
    dp = [0 for _ in range(1001)]
    dp[1] = 1 ; dp[2] = 2 # 2 * n 크기의 타일 초기값 설정해주기
    for i in range(3,input_n+1) :
        dp[i] = dp[i-1] + dp[i-2]
    print(dp[input_n] % 10007)