Notice
Recent Posts
Recent Comments
Link
컴퓨터는 잘못이 없다..
[알고리즘]BOJ_11726_2xn 타일링(파이썬 continue, 다이나믹 프로그래밍, 나머지 연산) 본문
Contents
접기
#문제 링크
#문제
https://www.acmicpc.net/problem/11726
2×n 타일링
시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 79385 29520 21526 34.903%
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
2
예제 출력 1
2
예제 입력 2
9
예제 출력 2
55
#답안
import sys
input=sys.stdin.readline
#n을 입력받는다.
n=int(input())
#dp테이블을 생성해놓고 0으로 초기화한다.
dp=[0]*(n+1)
#for문은 1부터 n까지 돌린다.
for i in range(1,n+1) :
if i==1 :
dp[1] = 1
continue
elif i==2 :
dp[2] = 2
continue
dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%10007)
▲답안 설명
앞서 만든 타일들에 가장오른쪽에 가로로 혹은 세로로 붙여서 타일을 만들다 보면
d[n]=d[n-1]+d[n-2]라는 식이 나온다!(d[n]은 2*n직사각형을 채우는 방법의 수)
'공부 > 알고리즘(파이썬)' 카테고리의 다른 글
Comments