(3) [C++, Java] 백준 No.11727 : 2xn 타일링2

문제

풀이

- 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-4-다이나믹-프로그래밍-문제-풀이3

# C++(Top-down방식)

#include <iostream>

using namespace std;

int d[1001] = {1, 1};   // d[0] = 1, d[1] = 1, d[0~99] = 0

// d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함.
// d[1] = 1; 원래 d[1]은 1이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        d[n] = getAllCombiCount(n-1) + 2 * getAllCombiCount(n-2);
        d[n] = d[n] % 10007; // 이렇게 해주면 d[i]에는 10007 미만의 수만 들어가게 된다.
        return d[n];
    }
}

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

# C++(Bottom-up방식)

#include <iostream>

using namespace std;

int d[1001] = {1, 1};   // d[0] = 1, d[1] = 1, d[0~99] = 0

// d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함.
// d[1] = 1; 원래 d[1]은 1이라서.

// N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수
int getAllCombiCount(int n)
{
    if (n <= 1)
        return d[n];
    
    else if (d[n] > 0)  // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환
        return d[n];
    
    else
    {
        for(int i=2; i <= n; i++)
        {
            d[i] = d[i-1] + 2*d[i-2];
            d[i] = d[i] % 10007; // 이렇게 해주면 d[i]에는 10007 미만의 수만 들어가게 된다.
        }
        return d[n];
    }
}

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

# Java

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[1001];
        d[0] = 1;
        d[1] = 1;
        for (int i=2; i<=n; i++) {
            d[i] = d[i-1] + d[i-2]*2;
            d[i] %= 10007;
        }
        System.out.println(d[n]);
    }
}