Memento's Programming

문제 2×n 크기의 직사각형을 1×2, 2×1, 2 x 2 타일로 채우는 방법의 수를 10007로 나눈 나머지를 출력하는 프로그램을 작성하시오. 풀이과정 이 문제는 지난 11726번 2xn 타일링 문제를 참고하면 좋을 것 같습니다. 단지 여기서 정사각형 모양의 2 x 2 타일이 추가된 것 뿐이지요. 지난 포스팅에서는 n = 3 일 때, n = 2 일 때 채웠던 방법들에 2 x 1 타일을 붙여주었습니다. 또한, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 정사각형 모양으로 붙여주었습니다. 여기서 우리는 추가로 n = 1 일 때 채웠던 방법들에 2 x 2 타일을 붙여줄 수 있습니다. 즉, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 붙여줄 수도 있고, 2 x 2 타일을 붙여줄 수 있..

문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 10007로 나눈 나머지를 출력하는 프로그램을 작성하시오. 풀이과정 이 문제 역시 DP로 풀 수 있는 문제입니다. n = 1 일 때는 2 x 1 타일로 채우는 한 가지 방법이 있습니다. n = 2 일 때는 2 x 1 타일 2개로 채우거나, 1 x 2 타일 2개로 채우는 방법이 있겠지요. 그럼 n = 3 일 때는 어떨까요? n = 2 일 때 채웠던 방법들에 2 x 1 타일을 추가할 수 있을 것입니다. 또한, n = 1 일 때 채웠던 방법들에 1 x 2 타일 2개를 정사각형 모양으로 추가할 수 있습니다. 이런식으로 (n - 1) 일 때의 가짓수와 (n - 2) 일 때의 가짓수를 더하면 n일 때의 가짓수를 쉽게 구할 수 있습니다. 이를 ..