[BOJ] 2133 풀이 C++/Java

문제

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

 

풀이

문제 이해하기

우선 문제를 이렇게 바꿔보자. 3xN칸 채우기 → 두 자연수의 합으로 N을 만들기

N=3이라고 했을 때, 3을 만드는 방법은 1+2, 2+1이 있다.

N=4라고 하면, 4를 만드는 방법은 1+3, 2+2, 3+1이 있다.

N=6, 6을 만드는 방법 1+5, 2+4, 3+3, 4+2, 5+1

...

이런 식으로 진행이 된다.

 

이제 3xN칸을 채워보자

 

3x1을 채울 수 있는 방법은 어떻게 채워도 존재하지 않는다.

3x2를 채우는 방법은 위의 그림과 같이 3가지 존재한다.

 

3x3은 1+2, 혹은 2+1, 3 이렇게 채울 수 있다.

1을 채우는 방법이 존재하지 않으므로, 1+2, 2+1로 채우기는 불가능하다.

3을 채우는 특별한 방법이 존재할까?

1x2, 2x1블럭 4개를 이용하면 2x4=8칸을 채울 수 있다. 5개를 이용하면 10칸을 채울 수 있다.

3x3=9칸을 채우는 방법은 존재하지 않는다. 

 

3x4를 채우는 방법. 4 = {1+3, 2+2, 3+1, 4}

이 중에서 1, 3을 이용하여 만드는 방법은 존재할 수 없으므로, {2+2, 4}의 경우만 살펴보면 된다.

1. 2+2를 채우는 경우
   • 3x2를 채우는 경우의 수는 3가지이다. 1, 2, 3으로 두 자리 수를 만드는 경우를 생각하면 쉽다.
   • 11, 12, 13, 21, 22, 23, 31, 32, 33 이렇게 9가지 경우가 나온다.
2. 4를 채우는 경우: 1x2를 얼기설기 배치한 형태(그림참고) = 다시 말해, 3x2 + 3x2의 경계에 1x2블럭을 배치하는 경우

2+2를 채우는 경우 9가지와 4를 채우는 특수한 경우 2가지를 합하여 총 11가지 경우가 나오게 된다.

 

 

이제 3x6을 채우는 경우를 생각해보자.

 

6= {1+5, 2+4, 3+3, 4+2, 5+1, 6}

이 중에서 1, 3, 5를 채우는 방법은 존재하지 않는다. 따라서 {2+4, 4+2}의 경우만 고려해서 생각해본다.

1. 2+4: 3x2를 채우는 방법 3가지 * 3x4를 채우는 방법 11가지 = 33가지
2. 4+2: 중복이 있으면 안 되므로 3x4를 채우는 특수 경우만 따로 고려. 3x2를 채우는 방법 3가지 *3x4를 채우는 특수 경우 2가지 =6
3. 6: 6을 채우는 특수 경우: 2가지

=> 33+6+2=41 

 

 

마지막으로 3x8의 경우를 살펴보자.

8={1+7, 2+6, 3+5, 4+4, 5+3, 6+2, 7+1, 8}

이 중에서 1, 3, 5, 7을 채우는 방법은 존재하지 않는다. 따라서 {2+6, 4+4, 6+2, 8}의 경우만 고려해서 생각해본다.

1. 2+6: 3x2를 채우는 방법 3가지 * 3x6를 채우는 방법 41가지 = 123가지
2. 6+2: 중복이 있으면 안 되므로 3x6를 채우는 특수 경우만 따로 고려. 3x6을 채우는 특수 경우 2가지 *3x2를 채우는 경우 3가지 =6
3. 8: 8을 채우는 특수 경우: 2가지
4. 4+4: 3x4를 채우는 모든 경우의 수 11가지 * 3x4를 채우는 특수 경우 2가지 = 22

이해를 돕기 위해 4+4 부분만 보충설명 해보겠다.

 

위의 22가지 경우가 있는데, 왜 좌우반전한 것은 경우의 수로 체크하지 않는걸까?

: 3x2 + 3x6을 채울 때 좌/우 중 하나는 고려되었기 때문

 

=> 123+6+2+22=153

 

 

점화식 세우기

홀수의 경우는 존재할 수 없으므로 바로 0출력 후 리턴

 

초기값

dp[1]=0;

dp[2]=3;

 

점화식

dp[i] = dp[i - 2] * 3 + dp[i - 4] * 2 + dp[i - 6] * 2 ... dp[0] * 2;

 

dp[i]=dp[2]*dp[i-2]; //(8=6+2)했던 것

 

dp[i]+=dp[i-4]*2 // 8=(4+4) 2+6에서 좌우반전이 고려되지 못한3*4의 특수 경우 2가지

dp[i]+=dp[2] *2 // 8=(2+6(6의 특수 경우))

dp[i]+=dp[0]*2 // 8의 특수 경우 2가지

 

 

dp[i] = dp[i - 2] * 4 - dp[i - 4]도 가능

https://www.acmicpc.net/board/view/134579

 

 

코드

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 홀수는 만들 수 없음
        if(n%2!=0){
            System.out.println(0);
            return;
        }

        int[] dp = new int[n+10];

        // 초기값
        dp[0]=1;// 아무것도 채우지 않는 경우 1개(아무 블럭도 배치하지 않으면 됨)
        dp[1]=0;
        dp[2]=3;

        // 전개
        for (int i = 4; i <= n; i+=2) {
            dp[i]=dp[2]*dp[i-2];

            // dp[0]*2= 각 단계에서만 나오는 특수 경우
            // dp[2]~dp[i-4] * 2는
            // dp[2]*dp[i-2]와 dp[i-2]*dp[2]에서 중복 경우를 제외한 경우
            // 즉 특수한 2가지 경우를 좌우반전한 경우를 의미
            for (int j = 0; j <= i-4 ; j+=2) {
                dp[i] += dp[j]*2;
            }
        }

        // output
        System.out.println(dp[n]);
    }
}

 

C++

#include <iostream>

using namespace std;

const int MAX_N = 30;

int n;
int dp[MAX_N+1];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    // 홀수를 채우는 방법은 존재하지 않음
    if(n%2!=0) {
        cout << 0 <<'\n';
        return 0;
    }

    //초기값
    dp[0]=1;
    dp[1]=0;
    dp[2]=3;

    // 전개
    for(int i=4; i<=n; i+=2){
        dp[i] = dp[2] * dp[i-2];

        for(int j=0; j<=i-4; j+=2){
            dp[i]+=dp[j]*2;
        }
    }

    // output
    cout << dp[n]<< '\n';

    return 0;
}