[BOJ] 백준 11726번: 2xn 타일링, 타일링 문제

www.acmicpc.net/submit/11726/21279055

로그인

타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다.

타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다.

아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다.

각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다.

여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다.

좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다.

점화식은 피보나치 형태임을 알 수 있습니다.

다르게 생각해보면 n에 대하여 n-2에서 겹치지 않게 블럭을 추가할 수 있는 경우는 아래모양으로 추가하는 방법밖에없습니다. ( d[i] = d[i-2] )

1x2 블럭 두개를 쌓은 모양

만약 2x1 블럭 두개를 이어버리면 (아래 블록) n-1에서 2x1 블럭이 맨뒤에오는 경우와 중복되는 경우가 생기게되므로 항상 n-2를 구성하는 경우에 1x2 블럭 두개를 쌓은 형태로 쌓아야합니다.

2x1 블럭 두개를 이은 모양

n-1에서는 1x2 블럭을 추가할 수 없으므로 1x2 블럭한개를 이어야 합니다. ( d[i] = d[i-1] )