고정 헤더 영역
상세 컨텐츠
본문
🔥 문제 링크
https://www.codetree.ai/missions/2/problems/rectangle-fill?utm_source=clipboard&utm_medium=text
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
🔥 문제
🔥 풀이
✅ 몇 번 계산하다 보면 쉽게 점화식 규칙이 보이는 문제이다.
| n | 사각형을 채우는 방법의 수 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
⚠️ 마지막에 %10,007로 나누어야 한다는 조건을 잊지 말자
🔥 코드
def dp(i):
if memo[i] != 0:
return memo[i]
memo[i] = (dp(i-1)+dp(i-2))%10007
return memo[i]
n = int(input())
memo = [0]*(n+1)
memo[1] = 1
memo[2] = 2
print(dp(n))
🔥 사이트 별 같은 문제
이 문제는 DP 기본의 정석같은 느낌... 이전에 다른 사이트에서도 풀었었음
누군가 필요할 수도 있으니 한 번 모아보았다
더 찾으면 추가할 것
(1) [ 백준 / 11726 ] 2*n 타일링
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
(2) [ 코드업 / 3709 ] 블럭 채우기1
https://codeup.kr/problem.php?id=3709&rid=0
블럭 채우기 1
$2*n$의 직사각형을 채울 수 있는 방법의 수에 $100,000,007$으로 나눈 나머지를 출력하시오.
codeup.kr
'알고리즘 > 코드트리' 카테고리의 다른 글
| [코드트리/INTERMEDIATE LOW] DFS 안전지대 Python 파이썬 (0) | 2023.08.09 |
|---|---|
| [코드트리/INTERMEDIATE LOW] Simulation 1차원 바람 Python 파이썬 (0) | 2023.08.07 |
| [코드트리/INTERMEDIATE LOW] DP I 계단 오르기 Python (0) | 2023.08.03 |
| [코드트리/INTERMEDIATE LOW] Simulation 양수 직사각형 최대 크기 Python (0) | 2023.08.02 |
| [코드트리/INTERMEDIATE LOW] Backtracking K개 중 하나를 N번 선택하기 Python (0) | 2023.08.01 |
