[JAVA] 백준 13699 점화식

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

13699번: 점화식

 
1. 서론
 
실버 4인데... 두 가지 고비가 있었던 문제다. 첫 번째: 점화식 구현. 두 번째: 자료형. DP 유형이라 실 4 임에도... 쉽지 않았다는 ㅜㅜ
 
2. 문제 풀이
 
문제에서 대놓고 식을 준다. 식을 보고서는 DP로 구현하는구나 깨닫게 된다..
근데 대놓고 식을 줘도 내 부족한 머리로는 한참을 고민했고 결국 식을 도출해 냈다.
 
t(0) = 1인 것은 고정이므로 처음 값을 미리 이렇게 설정해 두고,
반복문을 돌면서 n을 구하기 위해서 t(0), t(1),... t(n)을 순차적으로 구한다. DP를 구하는 방법은 탑다운 방식과 바텀업 방식이 있는데 이 문제의 점화식을 토대로 결국 t(n)을 구하는 것이 문제이기 때문에 바텀업 방식을 택했다.
반복문을 돌면서 t(n)까지 구하는데 점화식에 따르면
 
 

• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5

 
t(3)을 구하기 위해서는 
t(0)*t(2) - 2개
t(1)*t(1) - 1개
가 필요하다.
 
즉,
 
 

• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

 
 
아래의 점화식에서 t(0) * t(n - 1)  -> t(1) * t(n - 2) 이런 식으로 항목이 일정하게 커지고 어느 시점이 지나면 데칼코마니처럼 식이 반복되기 때문에 나는 절반만 계산하고 곱하기 2를 해서 두 배로 만들어줬다. 그리고 홀수인 경우에는 2로 나누어 떨어지지 않기 때문에 가운데 값을 따로 더해줬다.
 
그렇게 난 문제를 풀었고 테케를 다 맞아서 코드를 돌렸는데... 틀렸다. 98%까지는 맞았는데..
 

import java.io.*;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
    int n = Integer.parseInt(br.readLine());

    long [] dp = new long[n + 1];
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
      int idx = i - 1;

      for (int j = 0; j < i / 2; j++)
        dp[i] += dp[j] * dp[idx--];

      dp[i] *= 2;

      if (i % 2 != 0)
        dp[i] += dp[i / 2] * dp[i / 2];
    }

    System.out.print(dp[n]);
  }
}

 
이게 문제의 틀린 코드다. 테케는 잘 돌는데 왜 틀리는 걸까? 테케에 있던 25까지 통과했으면 괜찮지 않나?라고 생각했는데 아니었다.
질문 게시판을 보다가 안건데 n이 35까지이기 때문에 long이라는 자료형으로는 부족했다. C++은 longlong이 있어서 똑같지 않을까 했는데 Java는 longlong은 없고 BigInteger라는 자료형이 있어서 그걸 써서 구현했다.
 
3. 코드 설명
 

import java.io.*;
import java.math.BigInteger;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());

    BigInteger[] dp = new BigInteger[n + 1];
    dp[0] = BigInteger.ONE;
    
    for (int i = 1; i <= n; i++) {
      int idx = i - 1;
      dp[i] = BigInteger.ZERO;

      for (int j = 0; j < i / 2; j++)
        dp[i] = dp[i].add(dp[j].multiply(dp[idx--]));

      dp[i] = dp[i].multiply(BigInteger.valueOf(2));

      if (i % 2 != 0)
        dp[i] = dp[i].add(dp[i / 2].multiply(dp[i / 2]));
    }

    System.out.print(dp[n]);
  }
}

 
BigInteger 자료형으로 값들을 저장했다. BigInteger로  기본 값인 0과 1을 세팅했다.
그리고 위에서 작성했던 식을 BigInteger로 변환해서 적용했다.