[1793번] 타일링

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BigInteger

2. 점화식

자바 라이브러리 BigInteger를 이용하여 해결하면 간단하게 해결된다.

점화식은 다음과 같다. 

i-2번째에서 가로 직사각형(1x2)짜리를 2개 넣어 i번째를 완성, 2x2짜리 정사각형을 1개 넣어 i번째를 완성하거나

i-1번째에서 세로 직사각형(2x1)짜리 1개를 넣어 완성하면 된다.

따라서 DP[i] = DP[i-2]*2 + DP[i-1]이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import java.math.BigInteger; import java.util.Scanner;   public class Main {     public static void main(String []args)     {         int n;         BigInteger []DP = new BigInteger[251];         DP[0] = new BigInteger("1");         DP[1] = new BigInteger("1");         DP[2] = new BigInteger("3");           for(int i = 3; i <= 250; i++)         {             DP[i] = DP[i-2].multiply(new BigInteger("2"));             DP[i] = DP[i].add(DP[i-1]);         }                  Scanner sc = new Scanner(System.in);                    while(sc.hasNextInt())           {              n = sc.nextInt();                System.out.println(DP[n]);           }     } }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus