BOJ-백준 11727번 2xn 타일링 2 C++

BOJ-백준 11727번 2xn 타일링 2 C++ 문제 풀이 입니다.

링크 : https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>

int dp[1001];

int tile(int x) {
  if (x==1) return 1;
  if (x==2) return 3;
  if (dp[x]!=0) return dp[x];
  return dp[x] = (tile(x-1) + 2*tile(x-2))%10007;
}

using namespace std;
int main() {
  int n;
  cin >> n;
  cout << tile(n);
}

 

📌 해결 과정

다이나믹 프로그래밍 문제입니다. 이전 타일링 문제와 동일하게 규칙을 찾고 점화식을 세워 해결하는 문제입니다. 

이전의 타일링 문제에서 달라진 점은 정사각형 모양의 2x2 타일 종류가 더 생겼다는 점입니다.

 

우선, n-1길이의 타일에서 1 증가하여 n길이가 된 타일을 생각해봅시다.

세로로 긴 타일 1개를 붙이는 경우의 수 외에 다른 타일을 붙일 수 없습니다.

 

 

 

 

n-2 길이의 타일에서 2 증가하여 n길이가 된 타일을 생각해봅시다.

가로로 긴 타일 2개를 붙이는 경우의 수(왼)와 정사각 모양 타일 1개를 붙이는 경우의 수(오)가 있습니다.

따라서 n-2에서의 경우의 수에 2가지 경우의 수가 생기게 됩니다. 

 

이를 통해 길이가 n일때 타일을 붙이는 경우의 수는 n-1의 경우의 수와 n-2의 경우의 수의 두 배를 합한 것과 같습니다. 

점화식은 dp[n] = dp[n-1] +2*dp[n-2] 입니다. 

 

 

 

 

 

🚩 주의

n이 1일때의 경우의 수는 1, n이 2일때의 경우의 수는 3입니다.

n이 1000까지 입력될 수 있으므로 배열의 길이를 1001까지 선언하도록 합니다. 

오버플로우 방지를 위해 %10007 연산을 잊지 않고 해줍니다!

 

 

int dp[1001];

int tile(int x) {
  if (x==1) return 1;
  if (x==2) return 3;
  if (dp[x]!=0) return dp[x];
  return dp[x] = (tile(x-1) + 2*tile(x-2))%10007;
}

1. 재귀함수 tile을 작성합니다. 

종료 조건을 만들고 ( x == 1 일때 1 리턴, x == 2 일때 3 리턴)

dp 배열에 저장된 값이 있을때(0이 아닐때)  dp[x] 를 리턴합니다.

저장된 값이 없으면 재귀함수를 호출하며 dp를 구합니다. 

dp에 값을 넣기 전 %10007연산을 통해 오버플로우를 방지합니다. 

 

int main() {
  int n;
  cin >> n;
  cout << tile(n);
}

2. main에서 n 을 입력받고 tile함수를 호출하여 결과를 출력합니다. 

 

 

 

::