BOJ-백준 14852번 타일 채우기 3 C++

BOJ-백준 14852번 타일 채우기 3 C++ 문제 풀이 입니다.

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

10989번: 수 정렬하기 3

 

 

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

#include <iostream>
using namespace std;

long long int dp[1000001][2];

long long int cal_dp(int x){
  for(int i =3; i<=x; i++){
    dp[i][1] = (dp[i-3][0] +dp[i-1][1])%1000000007;
    dp[i][0] = (3*dp[i-2][0]+2*dp[i-1][0]+2*dp[i][1])%1000000007;
  }
  return dp[x][0];
}

int main() {
 dp[0][0] = 0;
 dp[1][0] = 2;
 dp[2][0] = 7;
 dp[2][1] = 1;
 int n;
 cin >> n;
 cout << cal_dp(n);
}

 

📌 해설

다이나믹 프로그래밍 문제 입니다.

점화식을 구하는 과정입니다. 

 

높이 2 너비 n-1인 벽이 1만큼 늘어나 n인 벽이 있다고 생각해봅시다. 

늘어난 만큼의 벽에 타일을 채울 수 있는 경우의 수는 2가지 입니다.

 

높이 2 너비 n-2인 벽이 2만큼 늘어나 n인 벽이 있다고 생각해봅시다.

늘어난 만큼의 벽에 타일을 채울 수 있는 경우의 수는 총 7가지 입니다.

단, 오른쪽 하단 4가지는 n-1에 포함된 경우의 수 이므로 n-2의 고유한 경우의 수는 3가지 입니다. 

여기 까지 점화식을 세운다면

dp[n] = 2*dp[n-1] + 3*dp[n-2] 입니다. 

예외가 더 있을 수 있으니 확인 해 봅시다.

높이 2 너비 n-3인 벽이 3만큼 늘어나 n인 벽이 있다고 생각해봅시다.

늘어난 만큼의 벽에 타일을 채울 수 있는 고유한 경우의 수는 2가지 입니다.

(중복되는 경우의 수 포함 시 총 22가지)

 

높이 2 너비 n-4인 벽이 4만큼 늘어나 n인 벽이 있다고 생각해봅시다.

늘어난 만큼의 벽에 타일을 채울 수 있는 고유한 경우의 수는 2가지 입니다.

 

이를 통해 알 수 있는 점화식은

dp[n] = 2*dp[n-1] + 3*dp[n-2] + 2*dp[n-3] + 2*dp[n-4] + ... + 2*dp[1] + 2*dp[0] 입니다.

(dp[n] = 2*dp[n-1] + 3*dp[n-2] + 2*(Sum(n-3))

 

 

🚩 주의

위 점화식을 이전 게시글의 타일링 문제 처럼 재귀함수 호출로 구현한다면 아래와 같이 프로그래밍 할 수 있습니다. 

#include <iostream>
using namespace std;

int dp[1000001];

int cal_dp(int x){
  if (x==0) return 1;
  if (x==1) return 2;
  if (x==2) return 7;
  if (dp[x]!=0) return dp[x];
  int result_dp = 3*cal_dp(x-2) + 2*cal_dp(x-1);
  for (int i=3; i <= x; i++){
    result_dp += 2*cal_dp(x-i);
  }
  return result_dp%1000000007;
}

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

위와 같이 재귀호출을 이용한 다이나믹 프로그래밍은 시간복잡도가 O(N^2)이기 때문에 해당 문제와 같이 n이 1,000,000 처럼 큰 숫자가 주어진다면 배열에 결과를 미리 저장 하더라도 시간이 매우 오래 걸립니다. 

시간초과를 피하기 위해 이차원 다이나믹 프로그래밍 기법을 사용하도록 합니다. 

 

 

#include <iostream>
using namespace std;

long long int dp[1000001][2];

1. 이차원 배열 dp를 선언해 줍니다. 

dp[x][0] 에는 dp 값이 들어가고,

dp[x][1]에는 dp[x-3][0]부터 dp[0][0]까지 합산된 값이 들어갑니다. 

 

int main() {
 dp[0][0] = 0;
 dp[1][0] = 2;
 dp[2][0] = 7;
 dp[2][1] = 1;
 int n;
 cin >> n;
 cout << cal_dp(n);
}

  2. dp를 초기화 합니다. 

dp[0][0] = 0, dp[1][0] =2, dp[2][0] = 7, dp[2][1] =1 입니다. 

3. n을 입력받은 뒤 dp를 계산합니다.

 

long long int cal_dp(int x){
  for(int i =3; i<=x; i++){
    dp[i][1] = (dp[i-3][0] +dp[i-1][1])%1000000007;
    dp[i][0] = (3*dp[i-2][0]+2*dp[i-1][0]+2*dp[i][1])%1000000007;
  }
  return dp[x][0];
}

 

4. 구해야 하는 dp 길이 만큼 반복하는 for문을 작성합니다. 

앞서 구한 점화식 (dp[n] = 2*dp[n-1] + 3*dp[n-2] + 2*(Sum(n-3))을 참고하여 반복문을 작성합니다. 

 

4-1. 구하고자 하는dp[x][0]을 구하려면 dp[x][1](= Sum(n-3))을 먼저 구해야 합니다. 

dp[x][1] = dp[x-3][0] + dp[x-1][1](=n-4까지의 합, Sum(n-4)) 입니다.

dp[x][0] =   2*dp[x-1][0] + 3*dp[x-2][0] + 2*(dp[x][1])

           =  2*dp[n-1] + 3*dp[n-2] + 2*(dp[x-3][0] + dp[x-1][1])

해당 값들을 %1000000007 연산 하여 오버플로우를 방지합니다. 

4-2. for문이 종료되면 dp[x][0]을 리턴합니다. 

 

 

::

이차원 DP ....ㅠ