(18) [C++, Java] 백준 No.2133 : 타일 채우기

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-19-DP-문제-풀이4-2-백준-No2133-타일-채우기

 

# C++

#include<iostream>

using namespace std;

int d[31];

int main()
{
    int n;
    cin >> n;

    d[0] = 1;

    for (int i = 2; i <= n; i+=2){           //(i=2, j=2), (i=4, j=2,4),  (i=6, j=2,4, 6)
        for(int j = 2; i-j >= 0; j+=2){
            if(j == 2)
                d[i] = 3 * d[i-j];
            else
                d[i] += 2 * d[i-j];
        }
    }

    cout << d[n] << "\n";
}

 

# Java

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