[백준 9095, Java] 1,2,3 더하기

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

풀이 

1. 단순재귀

- 입력의 최대가 11이므로 memoization이 없어도 시간초과가 나지않는다. 

[백준 9095, Java] 1,2,3 더하기

 

2. 점화식 

- 이 문제도 계단 오르기 문제와 비슷하다( n개의 계단을 1칸 또는 2칸이동하여 오르는 경우의 수). 문제의 최소단위가 1을 더하기, 2를 더하기, 3을 더하기이므로 f(n)= 1,2,3의 합으로 n을 나타내는 경우의수 로 정의하면 f(n) = f(n-1) + f(n-2) + f(n-3)으로 정의할 수 있다. 

 

 

check

- counts 배열을 선언할 때 크기를 n으로 하게되면 런타임 에러가 나는데 그 이유는 배열의 초기화를 index =2 까지 했기떄문이다. 다시말해 n=2 이게되면 Arrayarrayoutofboundsexception 예외가 발생한다. 

 

코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[] counts;
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt( br.readLine());
        for(int t= 0 ; t< T; t++){
            int N = Integer.parseInt(br.readLine().trim());
            counts = new int[12];
            counts[0] = 1;
            counts[1] = 1;
            counts[2] = 2;
            
            int count = makeNTopDown(N);
            bw.write(String.valueOf(count)+"\n");

        }
        bw.flush();
        br.close();
        bw.close();

    }
    public static void makeNbottomUp(int N ){
        for(int num = 3; num<=N ; num++){
            counts[num] = counts[num-1] + counts[num-2] + counts[num-3];
        }
    }

    public static int makeNTopDown(int N ){
        if (N <= 2) {
            return counts[N];
        }
        if(counts[N]>0){
            return counts[N];
        }
        counts[N] = makeNTopDown(N-1)+ makeNTopDown(N-2) + makeNTopDown(N-3);
        return counts[N];
    }
}