[SILER 3] 2xn 타일링

그림을 보면 가로 한칸을 채우는 방법은

1. 세로로 하나두기 (한칸차지)
2. 가로로 두개두기 (두칸차지) = 각항의 합이 n이 되도록 하는 1과 2로된 수열의 개수 구하는 문제

첫 예상

브루트포스 밖에 생각이 안났다. 안 그러고서야 풀수가 있나?..
대충 복잡도는 O(N^2) 이다. (대충 각칸마다 두갈래로 분기하니)
N <= 1000 이라 죽어도 불가능.

답, 풀이

어쩔 수 없이 분류를 깠고(DP) 그러고 나니 뭔가 알 것 같아서 몸이 움직이는데로 금방 풀었다.
구현상의 어려움은 아예 없었다.

#include<iostream>

int main() {
  int arr[1001];//1based
  for(int i = 0; i<= 1000; i++){
    arr[i] = 0;
  }
  arr[1] =1;
  arr[2] =1;

  for(int i = 1; i<=1000; i++) {
    int plusone = i+1;
    int plustwo = i+2;

    if(plusone <= 1000){
      arr[plusone] += arr[i];
      arr[plusone] %= 10007;
    }
    if(plustwo <= 1000){
      arr[plustwo] += arr[i];
      arr[plustwo] %= 10007;
    }
  }

  int N;
  std::cin >> N;

  std::cout << arr[N];
}

실제 DP문제로 정의해보기.

그러나 나의 풀이의 문제는

• 올바른 문제 정의 없이 감으로 풀었다.
• DP는 중복되는 계산을 메모이제이션으로 해결. 이 문제에서의 ‘중복’은?

일단 이 문제는 수열의 개수를 구하는 문제다. 하나하나 조합의 경우를 계산해낼 필요는 없을 것. 마치 100!이 서로다른 물건 100개를 나열하는 경우의 수이지만, 다 모든 케이스를 다 구하지 않 듯 말이다.

브루트 포스의 경우, 합이 i 인 수열에 대해 모두 다 계산한다.
ex) 1+2와, 2+1 모두 뒤에 남은 N-3칸은 동일한 배열만 들어갈 수 있다. 따라서 우리는.
합이 i일 모든 수열에 대해서 브루트 포스로 수열을 노가다로 하나하나 구해 합 ++ 하는게 아닌,
합이 i인 모든 수열 갑,을,병을 대충 합이 i인 수열 x개로 묶어도 문제 없는것이다.

(1) 문제 정의 :
DP(i) = 합이 i인 1과 2로만 이루어진 모든 수열의 개수.

(2) recurrence relation :
합이 i인 수열은, i-2, i-1 에서만 만들어 질 수 있다. 따라서
DP(i-1)+ DP(i-2) = DP(i);
그래서 dependeny 는 DP(i-1)과 DP(i-2)
base case는 DP(1) = 1, DP(2) = 2(1+1, 2)

(3) 시간 복잡도 :
베이스 케이스 초기화 = O(1) 모든 항 계산 = O(N) => O(N)

개선된 풀이

//최대 1000개의 블럭이 들어갈 수 있음.
//블럭을 1차원으로 채우는 방법의 경우의수 -> 가로로 쌓기(2칸), 세로로쌓기(1칸)
//1과 2로 만드는 합이 n인 수열의 개수.
//그러면 브루트 포스인것 같은데?..-> 복잡도가 말이안됨(약 2^n).
//해결 실패.

//문제의 태그는 다이나믹 프로그래밍
//아.. 굉장히 쉬운 문제 였다. 
//여기서 의문은 > 어떤 부분에 중복이 크게 있었기에 이를 DP로 해결하게 된걸까
//문제로써 구상의 의문이라 할 수 있겠다.

#include<iostream>

int main() {
  int arr[1001];//1based
  for(int i = 0; i<= 1000; i++){
    arr[i] = 0;
  }
  arr[1] =1;
  arr[2] =2;

  for(int i = 3; i<=1000; i++) {
    arr[i] = (arr[i-1] + arr[i-2])%10007;
  }

  int N;
  std::cin >> N;

  std::cout << arr[N];
}

DP정의에 맞게 구상하니 확실히 더 깔끔하고 이론에 근거한 코드가 작성되었다!

허나 찝찝한 점은 arr[2]라는 베이스케이스 계산을 위해서 매우 간단하지만 불편한 계산을 했다. (1+1, 2)

DP(i)의 정의에 따르면 합이 i인 수열의 개수! 합이 0이며 구분가능한 수열은 공집합이 있다! 따라서 진짜 베이스 케이스는 DP(0) = 1, DP(1) = 1.

최종 풀이

#include<iostream>

int main() {
  int arr[1001];//1based
  for(int i = 0; i<= 1000; i++){
    arr[i] = 0;
  }
  arr[0] =1;
  arr[1] =1;

  for(int i = 2; i<=1000; i++) {
    arr[i] = (arr[i-1] + arr[i-2])%10007;
  }

  int N;
  std::cin >> N;

  std::cout << arr[N];
}

알게된 점.

뭔가 DP라는 것을 전혀 알지 못하고 풀었는데 DP인 첫 문제 였던 것 같다.
DP 문제의 핵심은 어거지로 중복인 부분 찾기인 것 같다.
합이 N인 수열의 실제 값을 구할 필요가 없다(합이 N인 수열의 개수) 같은 문제의 허점을 파고들어서 말이다.