[백준] 13699. 점화식

문제 링크

[백준] 13699. 점화식

풀이 과정

다이나믹 프로그래밍(DP) 문제입니다. 문제에서 주어진 점화석대로 코드를 작성하면 됩니다.

t[0] 는 조건을 따르지 않고, t[1] 은 하나의 항으로 계산되므로 t[2] 부터 생각해보겠습니다.

t[2] 는 두 개의 항으로 계산합니다. 그 둘은 같으므로 위 사진의 점선을 기준으로 하나의 항만 구한 뒤, 그 값에 2를 곱하면 됩니다.

t[3] 은 총 세 개의 항으로 계산합니다. 홀수 개의 항이 등장하면, 정 가운데 점선 사각형을 기준으로 위 아래는 같은 값을 나타내며, 정 가운데의 항은 따로 계산 후 더해줍니다.

t[4] 는 총 네 개의 항으로 계산합니다. t[2] 와 마찬가지로, 점선을 기준으로 대칭되므로, 한 쪽만 구한 뒤 2를 곱하면 됩니다.

t[5] 는 총 다섯 개의 항으로 계산합니다. t[3]과 마찬가지로 가운데 점선 직사각형을 기준으로 대칭되므로, 한 쪽만 구해 2를 곱한 뒤, 직사각형에 해당하는 항을 따로 더해줍니다.

for (int i = 3; i <= n; i++) {
    long sum = 0;

    for (int j = 0; j < i / 2; j++) sum += t[j] * t[i - 1 - j];

    sum *= 2;
    t[i] = i % 2 == 0 ? sum : sum + t[i / 2] * t[i - i / 2 - 1];
}

따라서, 위처럼 코드를 작성할 수 있습니다.

• i 가 짝수면, j를 i의 절반까지 증가시키며 t[j] 값을 변수 sum 에 누적시킨 후, 그 값에 2를 곱합니다.
• i 가 홀수면, j를 i의 절반까지 증가시키며 t[j] 값을 변수 sum 에 누적시킨 후, 그 값에 2를 곱하고 정 가운데에 해당하는 항을 더해줍니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] t = new long[36];

        t[0] = t[1] = 1;
        t[2] = 2;

        for (int i = 3; i <= n; i++) {
            long sum = 0;

            for (int j = 0; j < i / 2; j++) sum += t[j] * t[i - 1 - j];

            sum *= 2;
            t[i] = i % 2 == 0 ? sum : sum + t[i / 2] * t[i - i / 2 - 1];
        }

        System.out.println(t[n]);
    }
}