티스토리 뷰
📌문제
가로가 N 세로가 2인 직사각형 형태의 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
📌풀이
1. 왼쪽부터 (i-1)까지의 길이가 덮개로 채워져있다면 2x1의 덮개를 채우는 하나의 경우
2. 왼쪽부터 (i-2)까지의 길이가 덮개로 채워져있다면 1x2 덮개 2개를 넣는 경우
2x2 덮개 하나를 넣는 경우
📌코드
n = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001
# 다이나믹 프로그래밍(보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796
print(d[n])
📌참고
'코딩테스트' 카테고리의 다른 글
최단 경로 (0) | 2024.11.03 |
---|---|
효율적인 화폐 구성 (1) | 2024.11.01 |
개미 전사 (2) | 2024.10.30 |
1로 만들기 (0) | 2024.10.29 |
다이내믹 프로그래밍 (5) | 2024.10.28 |