[SWEA] 4070 타일링

출처: [SWEA] SW 문제해결 심화 - 동적 계획법

 Input 

5

1

10

100

200

201

 

 Output 

#1 1

#2 683

#3 845100400152152934331135470251

#4 1071292029505993517027974728227441735014801995855195223534251

#5 2142584059011987034055949456454883470029603991710390447068501

 

Dynamic Programming (DP) 이용.

- 자세한 풀이는 [BOJ] 1793 타일링

[BOJ] 백준 1793 타일링

※ 1 ≤ N < 250 이기 때문에 DP[0]을 고려 X

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
         
        // 1 ~ 250
        BigInteger[] DP = new BigInteger[250 + 1];
         
        DP[1] = new BigInteger("1");
        DP[2] = new BigInteger("3");
         
        for(int i=3; i<=250; i++) {
            // DP[i] = (DP[i-1] + DP[i-2] * 2)
            DP[i] = DP[i-2].multiply(new BigInteger("2"));
            DP[i] = DP[i].add(DP[i-1]);
        }
         
        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());
            System.out.print("#" + tc + " ");
            System.out.println(DP[N]);
        }
    }
}