챕터3-3. DP | 문제 풀이1 - (2) 백준 No.11726 : 2xn 타일링

2xn 타일링 문제

https://www.acmicpc.net/problem/11726

문제요약

2xn 크기의 직사각형을 1x2, 2x1 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라

해결방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지"
             -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자.

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 2 x N의 직사각형이 주어지면 마지막 위치에 2가지 방법 중 1가지를 선택할 수 있다.

Case1) 세로로 1개를 놓는 경우
- 나머지 2 x (n-1) 크기의 직사각형을 채워넣어야 함

Case2) 가로로 2개를 놓는 경우
- 나머지 2 x (n-2) 크기의 직사각형을 채워넣어야 함

따라서, D[N] = D[N-1] + D[N-2] 으로 점화식을 생각할 수 있다. 이를 그림으로 살펴보면 아래와 같다.

ex) D[5] = D[4] + D[3]

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

4. 코드구현
- D[0] = 1, D[0] = 1 으로 두고 풀어야 함.
- d배열의 크기는 1001 이상 이어야 한다. 1<=N<=1000 이면 d[1000]이 존재해야 하기 때문이다.
- 출력할 때까지 다 가서 10007로 나눈 나머지를 구하면 안되는게 중간에 함수 반환 값이 int형의 범위를 넘어가기 때문이다.
   따라서, 애초에 d[n]에 10007로 나눈 나머지를 저장해야 한다. (int형은 +-20억까지의 범위를 가지기 때문)

* Top-Down, Bottom-Up 방식 모두 최종값이 결정되는 순서는 d[1], d[2], d[3],,, 순이다. (구현방식의 차이일 뿐)

<Top-down 방식>

(1) 구현
-> '재귀호출' 방식으로 구현

int d[1001] = {1, 1};   // d[0] = 1, d[1] = 1, d[0~99] = 0

// d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함.
// d[1] = 1; 원래 d[1]은 1이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        // 이렇게 해주면 d[i]에는 10007 미만의 수만 들어가게 된다.
        d[n] = (getAllCombiCount(n-1) + getAllCombiCount(n-2))% 10007;
        return d[n];
    }
}

(2) 시간복잡도
= 배열에 채워 넣어야하는 값의 수 x 1칸을 채우는 복잡도
= N x O(1) = O(N)

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

int d[1001] = {1, 1};   // d[0] = 1, d[1] = 1, d[0~99] = 0

// d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함.
// d[1] = 1; 원래 d[1]은 1이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for(int i=2; i <= n; i++)
        {
            // 이렇게 해주면 d[i]에는 10007 미만의 수만 들어가게 된다.
            d[i] = (d[i-1] + d[i-2])% 10007;
        }
        return d[n];
    }
}

int main()
{
    int n;
    cin >> n;
    cout << getAllCombiCount(n);
}

(2) 시간복잡도
= for 문의 반복 횟수 = O(N)