문제 출처 : www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
문제 해석 : 2X1 짜리 타일로 2XN의 타일을 채울 수 있는 방법의 수를 구하는 문제이다.
문제 풀이 : 이 문제는 DP로 풀 수 있다. 모든 경우는 앞에 있는 경우에 한쪽 끝에 타일이 붙은 것으로 생각할 수 있다. 이는 dp[i] = dp[i-1] + dp[i-2]라는 점화식으로 만들 수 있고 이를 그대로 활용하면 문제를 풀 수 있다.
풀이 코드
N = int(input())
dp = [0,1,2]
for i in range(3,N+1):
dp.append(dp[i-1]+dp[i-2])
print(dp[N]%10007)author : donghak park
contact : donghark03@naver.com
## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.
'📊알고리즘, 문제풀이 > 📈문제풀이 (PS)' 카테고리의 다른 글
| [알고리즘][Python] 백준 17219 비밀번호 찾기 문제 풀이 (3) | 2021.01.15 |
|---|---|
| [알고리즘][Python] 백준 11727 2xN 타일링 2 문제 풀이 (0) | 2021.01.15 |
| [알고리즘][Python] 백준 11724 연결 요소의 개수 문제 풀이 (0) | 2021.01.15 |
| [알고리즘][Python] 백준 11723 집합 문제 풀이 (0) | 2021.01.15 |
| [알고리즘][Python] 백준 11403 경로 찾기 문제 풀이 (0) | 2021.01.15 |