본문 바로가기

동적프로그래밍7

[👊DP뿌시기 #3] (BOJ 14852) 타일 채우기 3 https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. 접근법 저번 문제와 비슷하지만 1X1 피스가 생기면서 개복잡해졌다. N=1인 경우와 N=2인 경우는 위 그림처럼 각각 2개, 7개씩 나온다. N=3인 경우는 일단 N=2에 가로1 피스를 더한 경우와 N=1에 가로2 피스 중 (2x1, 1x1) 제외한 피스를 붙인 경우를.. 2023. 8. 15.

티스토리툴바