✅ DP ✅ Bottom up ✅ Top down

문제

링크

풀이

1. 문제 접근 및 해결 로직 (풀이법)

2xn 직사각형의 $i$ 번째에 직사각형을 채우는 방법은 두가지이다.
1. 세로 타일 (2x1)을 하나 둔다.
2. 가로 타일 (1x2)을 두개 둔다.

따라서 $i$ 번째를 채우는 방법의 수는
$2*(i타일을 채우는 방법의 수)$ 이다.

• 정의
  $f(i)=2*(i타일을 채우는 방법의 수)$
• 구하는 답
  $f(n)$
• 초기값
  $f(0)=1, f(1)=2$
• 점화식
  $f(i)=f(i-1)+f(i-2),(i>2)$

• 초기값
  0번째 : 세로 타일을 하나 두는 경우뿐
  1번째 : 세로 타일 두개 or 가로 타일 두개를 두는 경우가 있음

• 점화식
  $i$ 번째에 놓을 블록은 $i-1$ 번째와 $i-2$ 번째에 무슨 블록이 놓여 있는지에 따라 결정된다.

예를 들어 $(i-2)$ -> $(i-1)$ -> $(i)$ 순서대로 블록을 놓아보자.

1. $i-2$ 에 가로 블록을 놓았다면 가로 블록의 가로 사이즈가 2이므로 $i-1$ 에도 똑같은 가로 블록이고 $i$ 에는 세로 블록만 놓을 수 있다. (자동으로 결정)

2. $i-2$ 에 세로 블록을 놓았다면 $i-1$ 에는 세로, 가로 블록 둘 다 가능하고 $i$ 는 $i-1$ 에 어떤 블록을 놓았는지에 따라 자동으로 결정된다.

따라서 점화식은 $f(i)=f(i-1)+f(i-2),(i>2)$

2. 코드

- Bottom Up (반복문, 타뷸레이션)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    
    int block[n];
    block[0] = 1;
    block[1] = 2;
    
    for(int i = 2; i<n ; i++){
        block[i] = (block[i - 1] + block[i - 2]) % 10007;
    }
    
    cout << block[n-1] << "\n";

    return 0;
}

🔥 메모리초과

첫시도 때 for 문에서

block[i] = (block[i - 1] + block[i - 2])

block에 경우의 수를 그대로 삽입하여 풀었는데, 예제대로 정답은 잘 나오지만 백준에서 틀렸다고 나왔었다. 아마 뒤로 갈 수록 경우의 수가 너무 많아 메모리 문제가 발생한 것 같다.

문제의 출력 값으로 10007로 나눈 나머지를 구하라고 했으니 block에 경우의 수를 넣을 때도 10007로 나눈 나머지 값을 넣어 계산해도 점화식은 동일하므로 문제이 풀 수 있다.

- Top Down (재귀, 메모이제이션)

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int n;
int block[1001];

int cal(int n){
    if(n==0) return 1;
    if(n==1) return 2;
    
    if(block[n] != 0) return block[n]; // 이미 센것은 넘어감 (메모이제이션)
    
    block[n] = (cal(n-1) + cal(n-2)) % 10007; // 메모이제이션
    return block[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> n;
 
    block[0] = 1;
    block[1] = 2;

    cal(n-1);

    cout << block[n-1] << "\n";

    return 0;
}

🔥 시간초과

재귀함수에서 구한 값을 저장하고 (메모이제이션) 이후 같은 n번째의 경우의 수가 필요할 때는 같은 연산을 하지 않고 넘어가야 (이전에 구해서 저장해놨으므로 넘어가도 무방) 시간초과가 안남

3. 시간 복잡도 분석

$i$ 번째 경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항