백준 9461번 파도반수열

규칙에 따라 나선 모양으로 놓여진 정삼각형들 중 N번째 놓여진 정삼각형의 한 변의 길이를 구하는 문제다.

 

N번째 정삼각형의 한 변의 길이를 나열한다면 규칙을 쉽게 찾을 수 있다.

• P(1) = 1
• P(2) = 1
• P(3) = 1
• P(4) = 2 = P(2) + P(1)
• P(5) = 2 = P(3) + P(2)
• P(6) = 3 = P(4) + P(3)
• P(7) = 4 = P(5) + P(4)
• P(8) = 5 = P(6) + P(5)
• P(9) = 7 = P(7) + P(6)
• P(10) = 9 = P(8) + P(7)
• ...
• P(N) = P(N-2) + P(N-3)

import java.util.Scanner;

public class Main {

    static long dp = new long[101];

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        dp[1] = dp[2] = dp[3] = 1L;

        int T = in.nextInt();
        for (int tc = 0; tc < T; tc++) {
            int N = in.nextInt();
            System.out.println(padovan(N));
        }
    }

    public static long padovan(int n) {
        if (dp[n] != 0) {
            return dp[n];
        }

        return dp[n] = padovan(n - 2) + padovan(n - 3);
    }
}