백준 9095번 <1, 2, 3 더하기>

백준 알고리즘 9095번

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

9095번: 1, 2, 3 더하기

---

9095번

테스트 케이스의 개수가 주어지고  그 수만큼의 정수 n이 주어진다. 정수 n은 양수이며 11보다 작다.

---

문제 해결

처음에는 테스트케이스의 개수가 11보다 작은 건줄 알고 생각하고 있었는데

 

정수 n이 11보다 작은 거여서!!!

1부터 10까지의 1, 2, 3의 합으로 나타내는 방법의 수를 구해서 배열에 저장해두었다.

 

1, 2, 3의 합 구하는 방법

정수 n에서 1, 2, 3을 빼서 나온 수를 1, 2, 3의 합으로 나타내는 방법의 수를 다 더한다.

 

만약 정수 n이 4면

4 - 1 = 3 -> 3을 1, 2, 3의 합으로 나타내는 방법의 수와

1 + (3을 1, 2, 3의 합으로 나타내는 방법)

 

4 - 2 = 2 -> 2를 1, 2, 3의 합으로 나타내는 방법의 수와

2 + (2를 1, 2, 3의 합으로 나타내는 방법)

 

4 - 3 = 1 -> 1를 1, 2, 3의 합으로 나타내는 방법의 수를 더하면 결과가 나온다.

3 + (1를 1, 2, 3의 합으로 나타내는 방법

 

이때 1, 2, 3은 예외처리를 해주어야 한다.

일단 1은 1 1개고 (2, 3으로는 만들 수 없다.)

2는 3으로는 만들 수 없고 2만으로도 만들 수 있으니까!

3은 3만으로도 만들 수 있으니까!

---

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(br.readLine());

		int[] add = new int[11];

		for (int i = 1; i < 11; i++) {
			add[i] = -1;
		}
		add[1] = 1;
		for (int i = 2; i < 11; i++) {
			int sub = i - 1;
			int result = add[sub];

			if (sub == 1) {
				add[i] = result+1;
				continue;
			}

			sub = i - 2;
			result += add[sub];

			if (sub == 1) {
				add[i] = result+1;
				continue;
			}

			sub = i - 3;
			result += add[sub];
			add[i] = result;
			
		}
		
		for(int i = 0; i < num; i++) {
			int input = Integer.parseInt(br.readLine());
			System.out.println(add[input]);
		}
		
		

	}

}

---

---