[boj] (s3) 11726 2xn 타일링

25606 단어 bojboj

✅ DP ✅ Bottom up ✅ Top down

문제

링크

풀이

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

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

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

  • 정의
    f(i)=2(i타일을채우는방법의수)f(i)=2*(i타일을 채우는 방법의 수)
  • 구하는 답
    f(n)f(n)
  • 초기값
    f(0)=1,f(1)=2f(0)=1, f(1)=2
  • 점화식
    f(i)=f(i1)+f(i2),(i>2)f(i)=f(i-1)+f(i-2),(i>2)
  • 초기값
    0번째 : 세로 타일을 하나 두는 경우뿐
    1번째 : 세로 타일 두개 or 가로 타일 두개를 두는 경우가 있음

  • 점화식
    ii 번째에 놓을 블록은 i1i-1

예를 들어 (i2)(i-2)

  1. i2i-2

  2. i2i-2

따라서 점화식은 f(i)=f(i1)+f(i2),(i>2)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. 시간 복잡도 분석

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

4. 문제에서 중요한 부분

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

좋은 웹페이지 즐겨찾기