[boj] (s3) 11726 2xn 타일링
✅ DP ✅ Bottom up ✅ Top down
문제
풀이
1. 문제 접근 및 해결 로직 (풀이법)
2xn 직사각형의 번째에 직사각형을 채우는 방법은 두가지이다.
1. 세로 타일 (2x1)을 하나 둔다.
2. 가로 타일 (1x2)을 두개 둔다.
따라서 번째를 채우는 방법의 수는
이다.
- 정의
- 구하는 답
- 초기값
- 점화식
-
초기값
0번째 : 세로 타일을 하나 두는 경우뿐
1번째 : 세로 타일 두개 or 가로 타일 두개를 두는 경우가 있음 -
점화식
번째에 놓을 블록은 번째와 번째에 무슨 블록이 놓여 있는지에 따라 결정된다.
예를 들어 -> -> 순서대로 블록을 놓아보자.
-
에 가로 블록을 놓았다면 가로 블록의 가로 사이즈가 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. 시간 복잡도 분석
번째 경우의 수를 모두 구하므로
4. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
Author And Source
이 문제에 관하여([boj] (s3) 11726 2xn 타일링), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@peanut_/boj-s3-11726-2xn-타일링저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)