-
[이코테 다이나믹 프로그래밍] 바닥 공사Coding Test/이것이 코딩 테스트다 2021. 1. 10. 04:57
# 문제
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다.
# 입력
- 첫째 줄에 N이 주어진다. (1 <= N <= 1,000)
# 출력
- 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
# 입력 예시
3
# 출력 예시
5
내 풀이
n = int(input()) # dp 테이블 초기화 dp = [0] * 1001 # 다이나믹 프로그래밍 진행 (바텀업) dp[1] = 1 dp[2] = 3 for i in range(3, n + 1): dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 796796 print(dp[n])
'Coding Test > 이것이 코딩 테스트다' 카테고리의 다른 글
[이코테 다이나믹 프로그래밍] 금광 (0) 2021.01.10 [이코테 다이나믹 프로그래밍] 효율적인 화폐 구성 (0) 2021.01.10 [이코테 다이나믹 프로그래밍] 개미 전사 (0) 2021.01.10 [이코테 다이나믹 프로그래밍] 1로 만들기 (0) 2021.01.10 [이코테 이진 탐색] 고정점 찾기 (0) 2021.01.10