[ C++/cpp ] 백준 (11726 2×n 타일링) ⭐다이나믹프로그래밍

백준 11726번 2×n 타일링

(실버 3)

 

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

 

 

(정답 코드)

#include <iostream>
#include <vector>
#define MOD 10007 // 상수값은 깔끔하게 define 해두기

using namespace std;

// 피보나치 bottomup
int solution(int n) {
    vector<int> v (n+1, -1); // n+1칸 벡터 초기화
    v[0]=1;
    v[1]=1;
    
    for(int i=2; i<=n; i++) {
        v[i] = v[i-1] + v[i-2];
        v[i] %= MOD;
    }
    
    return v[n] % MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int n;
    cin >> n;
    
    cout << solution(n);

    return 0;
}

 

 

📖 풀이 

 

• N=1일 때, 2x1 크기의 직사각형을 채우는 방법은 1가지.
  • |ㅁ|
• N=2일 때, 2x2 크기의 직사각형을 채우는 방법은 2가지.
  • |ㅁㅁ| (세로로 2개)
  • |ㅡ| |ㅡ| (가로로 2개)
• N=3일 때, N=2에 1x2 타일 하나를 추가하는 방법과 N=1에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 3가지
  • |ㅁㅁ| |ㅁ|
  • |ㅁ| |ㅡ| |ㅡ|
  • |ㅡ| |ㅡ| |ㅁ|
• N=4일 때는 N=3에 1x2 타일 하나를 추가하는 방법과 N=2에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 5가지
  • |ㅁㅁ| |ㅁㅁ|
  • |ㅁㅁ| |ㅡ| |ㅡ|
  • |ㅁ| |ㅡ| |ㅡ| |ㅁ|
  • |ㅡ| |ㅡ| |ㅁㅁ|
  • |ㅡ| |ㅡ| |ㅡ| |ㅡ|
• N=5일 때는 N=4에 1x2 타일 하나를 추가하는 방법과 N=3에 2x1 타일 두 개를 추가하는 방법이 결합되어 총 8가지

 

 위 과정처럼, n = 1부터 한 5까지 벽돌 하나하나 그려보다보면 익숙한 규칙이 보이고 그건 바로 피보나치다. 전형적인 DP 문제 ! 사실상 피보나치 수열 구하는 문제다. 나는 DP 바텀업 방식으로 풀어보았다. 

 

 

 참고로 탑다운은 재귀로 구현하여 함수를 여러번 호출해야해서, for 반복문 한 번 도는 바텀업 방식이 더 빠르다~

 이번에 DP 다시 공부하면서 안 사실,, 바텀업 방식이랑 탑다운 방식이 시간 복잡도는 같아도, 바텀업 방식이 실제로 더 빠르다고 한다. 바텀업 방식이 반복문을 통해 한 번만 계산하는 반면, 탑다운 방식은 재귀 호출로 여러 번 계산하기 때문.

 

---

# 10007 나누기

 문제 요구사항 따라, 연산 중간중간 오버플로우 안나게 10007만 나눠주면 되어서 반복문마다 나눠줬다.  왜중간중간 나눠주어야 하냐면.. n 범위가 1000까지인데 피보나치 수열 1000번째 값은 .. 어마무시하다.

 

 

 참고로 연산 중간중간 나눠주어도 최종 값엔 영향이 없다. 두 수를 더한 후 나머지를 취하든, 나머지를 먼저 취한 두 수를 더하든 결과가 같다는 성질이 있기 때문.

ex. (7%3) + (9%3) = (7+9) % 3

이게 되나 맞나 싶을 땐 그냥  아무 숫자나 예시로 해보면 증명이 쉽다.

 

---

 

# 런타임 에러 - DoubleFree (double free or corruption)

 첨에 벡터 크기 n으로 해버려서, v[n] 접근하면서 런타임 에러가 떴다. 바보

너무도 기초적인 사실이지만.. n칸 인덱스까지 사용하려면 n+1칸을 초기화해야한다..ㅎ