[Silver IV] 점화식 - 13699 (JAVA)

문제 요약

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

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

이 정의에 따르면,

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

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

 

---

문제 분석

점화식 그대로 구현하며 dp를 사용한다.

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

이런 경우, 0과 1의 위치가 바뀐 같은 값을 연산한다는 것을 염두에 두고, 짝수와 홀수일 때를 나눠 계산해 준다.

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[] dp = new long[Integer.parseInt(br.readLine())+1];
        dp[0] = 1;
        for(int i = 1; i < dp.length; i++){
            for(int j = 0; j < i/2; j++){
                dp[i] += 2 * dp[j] * dp[i-j-1];
            }
            if(i%2 == 1){
                dp[i] += dp[i/2] * dp[i/2];
            }
        }
        System.out.println(dp[dp.length-1]);
    }
}

---

정리

새로 배운 내용

없음

개선할 점

없음

더 찾아볼만한 사항

없음

---