<Algorithm> 66. 11727번 2*n 타일링 2

1. 11727번 2*n 타일링 2

• 간단한 DP 문제, 점화식을 잘세워야 간단하게 풀 수 있는 문제

• 처음 접근을 재귀로 n이 15 정도 되니까 시간초과가 발생했다. 재귀로 풀고 답을 확인 후 식을 세우는 것도 하나의 방법일것 같다.

• 2 * (이전 인덱스) + 이이전 인덱스의 값을 하니 답이 나오는줄 알고 풀었지만 50이 넘어가는 경우 되지 않았다.

• 그래서 int형이라 오버플로우 때문인가 싶어서 BigInteger식이 틀린 것을 확인 할 수가 있었다.

• 2의 n을 이용할때 지수 n이 얼마나 커지는지 반드시 확인을 해야하고 10번의 테스트가 맞아도 틀리는 경우도 있다는 걸 상기해야 한다.

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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

import java.util.Scanner;   public class Main {     static int[] dp = new int[1 << 17];       public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = Integer.parseInt(sc.nextLine());         System.out.println(tiling(n));       }       /*      * public static int tiling(int n) {      * if(n == 0)       *     { return 1; }       * else if(n < 0)       *     { return 0; }      * return dp[n] = (tiling(n - 2) + tiling(n - 2) + tiling(n - 1))%10007;      * }      *      * public static int tiling(int n, int index) { dp[0] = 0; dp[1] = 1; dp[2] = 3;      *       * for(int i = 3; i <= n; i ++) {      *  dp[i] = ((int)(dp[i -2]+Math.pow(2,i-1)))%10007;       *  }      *   return dp[n];       *  }      */     /*      * @SuppressWarnings("static-access") public static BigInteger tiling(int n, int      * index) {       * BigInteger[] bg = new BigInteger[1001];       * BigInteger bi = new BigInteger("1");       *           * for(int i = 0; i < 1001;i++)       *  bg[i] = new BigInteger("1");      *       * bg[0] = bi.valueOf(0); bg[1] = bi.valueOf(1); bg[2] = bi.valueOf(3);       * for(int i = 3; i <= n; i ++) {       *     bg[i] = bg[i-2].add(bi.valueOf((long)Math.pow(2,i-1))); \      *     bg[i] = bg[i].mod(bi.valueOf(10007));       *   }       * return bg[n];      *       * }      */     public static int tiling(int n) {         dp[0] = 0;         dp[1] = 1;         dp[2] = 3;                  for (int i = 3; i <= n; i++) {             dp[i] = (dp[i - 1] + 2*dp[i - 2])% 10007;         }         return dp[n];     }   } Colored by Color Scripter

cs