[백준 9095]1, 2, 3 더하기 - 자바

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

1. 풀이

---

DP로 풀려고 노력했지만, 처음엔 규칙을 찾지못했는데, 5를 만드는 1,2,3을 더하는 경우의 수가 13임을 발견하고 규칙을 찾게 되었습니다.

 

규칙은 다음과 같습니다. D[N] = D[n-1] + D[n-2] + D[n-3]

 

 

2. 코드

---

2.1 Top-Down

import java.util.*;

public class Main {
	
	static int[] memo;
	
	public static int onetwothree(int n) {
		if(n < 0) 
			return 0;
		if(n <= 1)
			return 1;
		if(memo[n] != 0) // 이미 구한 값이라면 구한 값 반환.
			return memo[n];
		
		memo[n] = onetwothree(n-1) + onetwothree(n-2) + onetwothree(n-3);
		return memo[n];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		memo = new int[12];
		
		int input;
		int[] result = new int[num];
		for(int i = 0; i < num; i++) {
			input = sc.nextInt();
			result[i] = onetwothree(input);
		}
		
		for(int i = 0; i < num; i++)
			System.out.println(result[i]);
		
		sc.close();
		return;
	}
}

 

2.2 Bottom-Up

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		
		int[] memo = new int[12];
		
		memo[1] = 1;
		memo[2] = 2;
		memo[3] = 4;
		
		int n;
		int[] result = new int[num];
		for(int i = 0 ;i < num; i++) {
			n = sc.nextInt();
			for(int j = 4; j <= n; j++) {
				memo[j] = memo[j-1] + memo[j-2] + memo[j-3];
			}
			result[i] = memo[n];
		}
		
		for(int i = 0; i < result.length; i++)
			System.out.println(result[i]);
		
		sc.close();
		return;
	}
}