[백준] 11726번 2×n 타일링 C++ 풀이

---

알고리즘 분류

• DP

---

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

---

입력 설명

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

---

출력 설명

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

---

예제 입력

2

 

9

---

예제 출력

2

 

55

---

아이디어

n이 1일 때 1가지

n이 2일 때 2가지

n이 3일 때 3가지

n이 4일 때 5가지

...

n이 9일 때 55가지

 

이것을 보고 피보나치수열임을 알았다.

---

알고리즘

DP를 사용해서 기존에 이미 계산했던 값은 벡터에 저장해두어 중복 계산을 방지하며 재귀로 푼다.

또한 10007로 나눈 나머지를 저장하고 리턴하는 것도 잊지 말자.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int n;
long long recursion(vector<long long>&vec,long long n)
{
    if(n == 0) return vec[0];
    else if(n == 1) return vec[1];
    if(vec[n-1] == -1) vec[n-1] = recursion(vec,n-1)%10007;
    if(vec[n-2] == -1) vec[n-2] = recursion(vec,n-2)%10007;
    return  (vec[n-1] + vec[n-2])%10007;
}
int main() {
    cin>>n;
    vector<long long> vec(n+1,-1);
    vec[0] = 1;
    vec[1] = 1;
    cout <<recursion(vec, n);
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/11726

피보나치수열인 것은 빠르게 파악했지만

처음에는 DP를 사용하지 않고 재귀 함수만을 사용해서 풀어서 시간초과가 났다.

그래서 DP를 사용해서 풀었더니 맞았다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!