[백준 알고리즘] 백준 9095번 1, 2, 3 더하기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 9095번 1, 2, 3 더하기 자바(Java)

1) 문제번호 : 9095번

 

2) 문제 출처

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

2. 문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

3. 제약사항

- 

4. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

5. 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

6. 풀이

- 1부터 5까지 차례대로 구해보면 규칙이 생긴다.

- N-1 + N-2 + N-3 의 개수들을 더하면 N번째의 개수가 된다.

- 1은 1개, 2는 1+1, 2로 2개, 3은 1+1+1, 2+1, 1+2, 3 으로 3개 이런 식으로 구하면 된다.

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(); //테스트 케이스 개수
		
		for(int i=0;i<T;i++) {
			int N = sc.nextInt(); // 정수
			System.out.println(recur(N));			
		}
		
	}
	
	public static int recur(int N) {
		if(N==1) return 1;
		if(N==2) return 2;
		if(N==3) return 4;
		else return recur(N-3) + recur(N-2) + recur(N-1);
	}
}

 

---