백준 9095 (1, 2, 3 더하기)

문제

---

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

 

 

풀이

---

1 = 1

2 = 1+1, 2

3 = 1+1+1, 1+2, 2+1, 3

4 = 1의 경우에 3을 더함

      2의 경우에 2를 더함

      3의 경우에 1을 더함

5 = 2의 경우에 3을 더함

      3의 경우에 2를 더함

      4의 경우에 1을 더함

...

 

이런식으로 진행되는 걸 점화식으로 나타내면

 

a_n = a_n-1 + a_n-2 + a_n-3  

 

이 나온다.

 

<Bottom-Up 코드>

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

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int Case = Integer.parseInt(bufferedReader.readLine());
	    
		    for(int j = 0 ; j < Case ; j++) {
		    int n = Integer.parseInt(bufferedReader.readLine());
			
		    int[] dp = new int[12];
		    dp[1] = 1;
		    dp[2] = 2;
		    dp[3] = 4;
		    
		    for(int i = 4 ; i <= n ; i++) {
		    	dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
		    }
		    sb.append(dp[n] + "\n");
	    } 
	    System.out.println(sb);
	}
}

 

 

넥슨 코딩테스트에서 나온 문제와 비슷해서 재귀로도 풀어 보았다.

재귀형식으로 1, 2, 3 을 더해서 해당 값이 나오면 count를 해주는 방식으로 풀었다.\

 

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

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	static int count = 0;
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int Case = Integer.parseInt(bufferedReader.readLine());
	    
		    for(int j = 0 ; j < Case ; j++) {
		    int n = Integer.parseInt(bufferedReader.readLine());
			count = 0;
		    Calculator(0, n);
		    
		    sb.append( count + "\n");
	    } 
	    System.out.println(sb);
	}
	
	static void Calculator(int sum, int n) {
		if( sum == n) {
			count++;
			return;
		}
		else if(sum > n ) {
			return;
		}
		
		
		for(int i = 1 ; i <= 3 ; i++) {
			Calculator(sum+i, n);
		}	
	}
}