11727 : 2×n 타일링 2
문제2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다. 풀이방법방법은 11726과 거의 동일하다.먼저, d[n]을 어떻게 나눌 수 있을지 생각해봐야한다. d[n]은 아래 3가지 경우로 나눌 수 있다.1. 2x1 블록으로 끝나는 경우 2. 1x2 블록 2개로 끝나는 경우3. 2x2 블록 1개로 끝나는 경우 위의 3가지 경우를 다르게 표현하면 아래와 같다.1. d[n-1] 끝에 2x1 블록이 추가되는 경우 2. d[n-2] 끝에1x2 블록 2개가 추가되는 경우2. d[n-2] 끝에2x2 블록이 추가되는 경우 d[n] = d[n-1] + d[n-2] + d[n-2]즉, 식은 d[n] = d[n-1] + d[n-2] * ..
11726 : 2×n 타일링
문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 풀이방법먼저 식을 세워야하는데 d[n]을 어떻게 표현할 수 있을지 생각해보아야 한다. d[n]은 크게 2가지 경우로 나누어 질 수 있다. 1. 끝이 2x1 블록으로 끝나는 경우2. 끝이 1x2 블록 2개로 끝나는 경우 이 두가지 경우 외에 올 수 있는 경우는 없다. 이 두가지 경우를 다르게 말하면 아래와 같다. 1. d[n-1] 끝에 2x1 블록이 추가되는 경우2. d[n-2] 끝에 1x2 블록 2개가 추가되는 경우 따라서 식은 d[n] = d[n-1] + d[n-2]로 유추할 수 있다 출처 : https://www.youtube.com/..