117261 [BOJ] 백준 11726번: 2xn 타일링, 타일링 문제 www.acmicpc.net/submit/11726/21279055 로그인 www.acmicpc.net 타일링 문제는 동적 계획법을 접하면 입문 문제로 간단한 점화식으로 풀리는 문제입니다. 타일은 1x2 크기와 이것을 회전한 2x1 타일이 있으며, 길이 n이 주어질 때 2 x n 직사각형을 채울 수 있는 경우의 수를 찾아야 합니다. 아래는 n이 각각 1, 2, 3 인 경우를 보여줍니다. 각 경우에서 보면 빨간 블록은 이전 단계들의 블록 모양이며 파란색은 현재 단계에 새로 추가된 블록입니다. 여기까지만 보면 점화식을 d[i] = d[i-1] + d[i-2]로 유추해볼 수 있습니다. 좀더 정확하게 알아보기 위해 n이 4인 경우를 보면 n이 2인 경우 + n이 3인 경우의 합이 됩니다. 점화식은 피보나치 형태.. 2020. 9. 7. 이전 1 다음
