[BOJ 9095] 1,2,3 더하기 (java)

문제 링크 https://www.acmicpc.net/problem/9095

1) Top-down 풀이

package basics_400;

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

public class BOJ9095 {
	//memo[n] = n을 1,2,3의 합으로 나타내는 방법의 수 
	static int[] memo;
	static int plusNumber(int n) {
		//0을 1,2,3 으로 만드는 방법의 수 -> x 공집합 = 1가지 
		//1을 1,2,3 으로 만드는 방법의 수 => 1 = 1가지 
		if(n==0||n==1)
			return 1;
		
		//2를 1,2,3 으로 만드는 방법의 수 => 1+1, 2 = 2가지 
		if(n==2) 
			return 2;
		
		//이미 계산되어 있으면 계산할 필요 없음 
		if(memo[n]>0)
			return memo[n];
		
		//n이 3 이상일때,
		//ex) n=3 
		// 1 + 2를 1,2,3의 합으로 나타내는 방법의 수 
		// 2 + 1을 1,2,3의 합으로 나타내는 방법의 수
		// 3 + 0을 1,2,3의 합으로 나타내는 방법의 수 
		if(n>2) {
			memo[n] = plusNumber(n-1)+plusNumber(n-2)+plusNumber(n-3);
		}
		
		return memo[n];
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//테스트케이스 
		int tc = Integer.parseInt(br.readLine());
		
		while(tc>0) {
			//tc만큼 n입력 
			int n = Integer.parseInt(br.readLine());
			memo = new int[n+1];
			System.out.println(plusNumber(n));
			tc--;
		}


	}

}

2) Bottom-up 풀이

package basics_400;

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

public class BOJ9095_2 {
	static int[] memo;
	static int plusNumber(int n) {
		
		//0을 1,2,3 으로 만드는 방법의 수 -> x 공집합 = 1가지 
		//1을 1,2,3 으로 만드는 방법의 수 => 1 = 1가지 
		//2를 1,2,3 으로 만드는 방법의 수 => 1+1, 2 = 2가지 	
		memo[0] = 1;
		memo[1] = 1;
		memo[2] = 2;
		
		//n이 3 이상일때,
		//ex) n=3 
		// 1 + 2를 1,2,3의 합으로 나타내는 방법의 수 
		// 2 + 1을 1,2,3의 합으로 나타내는 방법의 수
		// 3 + 0을 1,2,3의 합으로 나타내는 방법의 수 
		for(int i=3;i<=n;i++) {
			memo[i] = memo[i-1]+memo[i-2]+memo[i-3];
		}
		
		return memo[n];
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//테스트케이스 
		int tc = Integer.parseInt(br.readLine());
		
		while(tc>0) {
			//tc만큼 n입력 
			int n = Integer.parseInt(br.readLine());
			memo = new int[n+2];
			System.out.println(plusNumber(n));
			tc--;
		}


	}

}