일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 스프링
- 파이썬
- SW봉사
- 백준 알고리즘
- 프로그래머스
- 자바
- 시나공
- 공부일지
- kotlin
- 데이터베이스
- programmers
- 코틀린
- 문제풀이
- python
- 코딩교육봉사
- 코딩봉사
- MYSQL
- softeer
- SQL
- 회고
- 알고리즘
- 정보처리산업기사
- CJ UNIT
- java
- 백준알고리즘
- 소프티어
- C++
- 백준
- 1과목
- BFS
- Today
- Total
JIE0025
[BOJ - DP] 11726번 : 2×n 타일링 ( python ) 본문
백준알고리즘 11726번 2×n 타일링 (다이나믹프로그래밍 / 동적 계획법) 파이썬
https://www.acmicpc.net/problem/11726
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
1. 사고하기
- 목표 : 2×n 크기의 직사각형을 채우는 방법의 수
- 유형 : DP
1x2, 2x1의 타일로 채우는 방법을 차례대로 생각해봤다.
- n = 1 (1가지)
- n = 2 (2가지)
- n = 3 (3가지) : 1번개수 + 2번개수
- n = 4 (5가지) : 2번개수 + 3번개수
...
dp[1] = 1
dp[2] = 2
즉 dp[i] = dp[i-1] +dp[i-2] (i >=3)
2. 이 문제를 공유한 이유
<비슷한 문제 but 다른 점화식 유도과정>
나는 단순히 n이 1인 경우 2인 경우 ... 4인경우까지 해서 점화식을 유도했는데
비슷한 문제의 풀이는 약간 달라서 공유해보았다.
이 문제에선 타일이 3개 존재한다.
유도하는 과정은 다음과 같다.
여기서 주의해야할점은 i-2까지 다 채워진 경우였다.
1경우와 같기 때문에 빼주었는데
그렇게 따지면 우리 11726문제도 i-2경우에 i-1경우와 동일한 것이 존재한다. (초록색 타일은 i-1의 경우와 같다)
당연히 위의 경우처럼 i-1의 경우를 고려해서 11726문제의 점화식을
a(i) = a(i-1) + a(i-2)라고 생각할 수 있다.
정답코드
import sys
input = sys.stdin.readline
n = int(input())
dp =[0] *1001
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[n])
'알고리즘 > 백준' 카테고리의 다른 글
[BOJ - 문자열] 1501번 : 영어 읽기 ( python ) (0) | 2022.04.28 |
---|---|
[BOJ - 그리디] 1049번 : 기타줄 ( python ) (0) | 2022.04.22 |
[BOJ - DP] 14916번 : 거스름돈 ( python ) (0) | 2022.04.12 |
[BOJ - 이분탐색] 16564번 : 히오스 프로그래머 ( python ) (0) | 2022.04.08 |
[BOJ - BFS] 1240번 : 노드 사이의 거리 ( python ) (0) | 2022.04.06 |