21.09.16 기록

백준 알고리즘 9461 풀이

🎆나의 풀이(메모리 14.1MB, 시간 120ms로 통과)

-(N-3번째 요소) + (N-2번째 요소) = N번째 요소 규칙을 사용하여 풀이했다.
-요소의 값이 계속 커지기 때문에 N값이 크면 int형 범위를 넘어가서 long 타입을 사용했다.
-해설도 큰 내용은 없어서 생략했다.

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

public class B9461 {
    public static Long[] triangle = new Long[100 + 1];

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

        triangle[0] = 0L;
        triangle[1] = 1L;
        triangle[2] = 1L;

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < testCase; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(P(N)).append("\n");
        }
        System.out.println(sb);
    }

    public static Long P(int N) {
        if(triangle[N] == null) {
            triangle[N] = (P(N-3)) + (P(N-2));
        }
        return triangle[N];
    }
}