프로그래머스에서 연습문제 몇 가지를 풀어보았다.

[문제] 2 x n 타일링

설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

타일을 가로로 배치 하는 경우
타일을 세로로 배치 하는 경우
예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
가로의 길이 n은 60,000이하의 자연수 입니다.
경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

풀이과정

종만북 252p 에 같은 문제가 있어서 쉽게 풀수 있었다.
완전 탐색을 이용하여 모든 답을 만들면서 개수를 세어보는 함수르 ㄹ작성 한 뒤, 메모이제이션을 이용해 동적계획법으로 바꾸었다. 이러한 경우의수를 셀 때 두 가지 속성을 항상 확인하여야한다.

두 가지 분류는 타일링하는 방법을 모두 포함한다.
두 가지 분류에 모두 포함하는 타일링 방법은 없다.

부분 문제 분할이 첫번째 조건을 위반시 알고리즘은 실제 수보다 적은 답을 내놓는다.
모든 수를 세려고 하는데 앞 뒤가 모두 같다고 생각되기 때문이다,
반대로 두번째 조건을 위반 시 실제보다 많은 답을 세게 되는데, 모든 수를 세려고 하는데 중복을 허용하기 때문이다. 다행히 이 문제는 두 가지의 성질이 성립한다. 따라서 타일 두 개로 덮을 것인지를 결정하기만 하면된다.

tiling(n) = 2 * n 크기의 사각형을 타일로 덮는 방법을 반환한다.
tiling(n) = tiling(n-1) + tiling(n-2)

이것을 통해 작성된 코드다.

#include <string>
#include <vector>

using namespace std;

const int mod = 1000000007;
int cache[60000];

int tiling(int width){
  if(width <= 1) return 1;
  
  int& ret = cache[width];
  if(ret != 0) return ret;
  return ret = (tiling(width-2) + tiling(width-1)) % mod;
}

int solution(int n) {
  int answer = 0;
  answer = tiling(n);
  return answer;
}