[BOJ]11726번: 2×n 타일링(java, c++)

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

11726번: 2×n 타일링

 

방법 1: Top-down

import java.io.*;
 
public class Main {
 
    public static int[] arrCount;
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            arrCount = new int[num + 1];
            
            System.out.println(calculate(num));
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    public static int calculate(int num) {
 
        if (num <= 2) {
            return num;
        }
 
        if (arrCount[num] > 0) {
            return arrCount[num];
        }
        
        arrCount[num] = calculate(num-1) + calculate(num-2);
        
        return arrCount[num] % 10007;
    }
}

import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            int[] arrCount = new int[1001]; // int[] arrCount = new int[n + 1] 에서 수정..런타임 에러..
            
            arrCount[1] = 1;
            arrCount[2] = 2;
            
            for (int i = 3; i < arrCount.length; i++) {
                arrCount[i] = (arrCount[i - 1] + arrCount[i - 2])  % 10007;
            }
            
            System.out.println(arrCount[num]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    const int DIV = 10007;
    const int MAX = 1000;
    int D[MAX + 1];
 
    D[0] = 1;
    D[1] = 1;
    
    // 점화식 : D[n] = D[n - 1] + D[n - 2]
    for (int i = 2; i <= n; i++)
    {
        D[i] = (D[i - 1] + D[i - 2]) % DIV;
    }
 
    cout << D[n];
 
    return 0;
}

 

 

이 문제는 탑다운 방식이 바텀업 방식보다 빨랐다. 

 

TIP1

2 * n 크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법이므로 

사각형을 놓는 방법은 2가지임을 알 수 있다. 

• 가로 길이가 1 늘어나는 방법
• 가로 길이가 2 늘어나는 방법

 

각 방법이 가로길이  ? 에서부터 증가시키는 것인지 파악하면 된다.

2 * n 를 채우는 방법의 수를 D(n) 이라 하면,

D(n) = D(n - 1) x 가로길이가 1 늘어나는 방법의 수

          + D(n - 2) x 가로길이가 2 늘어나는 방법의 수

 

이후는 피보나치 수열처럼 계산하면 된다. 

 

 

TIP2

int[] arrCount = new int[num + 1]; //( X )

배열을 선언할 때 입력받은 변수로 배열 길이를 대입하지 말자

 

int[] arrCount = new int[1001];  //( O )
            
arrCount[1] = 1;
arrCount[2] = 2;

초기 값 2개를 입력해 주어야 하므로,

만약 입력받은 수가 2보다 작다면 런타임 에러가 발생하게 된다.