[백준 1793] 타일링 - JAVA

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

 

Dp 기초 + 큰 수 연산

 

dp를 사용하므로 복잡도는 크지않아 빅인티저로 해결 가능

 

단, n=0일 때 1을 출력해야한다. 이에 대한 글이 있다.

https://www.acmicpc.net/board/view/33143

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input;

    while ((input = br.readLine()) != null) {

      int N = Integer.parseInt(input);

      BigInteger[][] dp = new BigInteger[N + 1][3];

      dp[0][0] = new BigInteger("0");
      dp[0][1] = new BigInteger("0");
      dp[0][2] = new BigInteger("0");

      if (N > 0) {
        dp[1][0] = new BigInteger("1");
        dp[1][1] = new BigInteger("0");
        dp[1][2] = new BigInteger("0");
      }

      if (N > 1) {
        dp[2][0] = new BigInteger("1");
        dp[2][1] = new BigInteger("1");
        dp[2][2] = new BigInteger("1");
      }

      for (int n = 3; n <= N; n++) {
        dp[n][0] = dp[n - 1][0].add(dp[n - 1][1]).add(dp[n - 1][2]);
        dp[n][1] = dp[n - 2][0].add(dp[n - 2][1]).add(dp[n - 2][2]);
        dp[n][2] = dp[n - 2][0].add(dp[n - 2][1]).add(dp[n - 2][2]);
      }

      System.out.println(N == 0 ? 1 : dp[N][0].add(dp[N][1]).add(dp[N][2]));
    }
  }
}