[Java] BOJ9095, 백준 - 1, 2, 3 더하기(재귀)

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

9095번: 1, 2, 3 더하기

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	62873	40439	26831	62.322%

문제

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

 

입력

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

 

출력

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

 

<풀이>

다이나믹으로 풀 때랑 방법은 같되, 함수만 재귀를 사용하였다.

1. 1, 2, 3을 뺄 수 있을 경우에( = 1, 2, 3을 빼더라도 음수가 되지 않는 경우)

2. 1, 2, 3을 빼면서 0이 될때까지 함수를 반복한다.

3. 종료조건: n이 0보다 작아졌을 때(음수인 경우는 1번에서 걸러주었으니, n<=0으로 조건 설정)

 

시간복잡도

n의 범위가 1부터 10까지기 때문에 최댓값인 10을 기준으로 생각한다.10인 경우에 재귀로 반복하는 최대 경우의 수는 함수 한 번 당 재귀가 세 번씩 반복되기 때문에3의 10제곱 = 6만정도로 시간제한인 1초에 충분히 풀 수 있다.

 

소스 코드

import java.io.*;

public class Main {
	private static int cnt;

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

		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			cnt = 0;
			go(n);

			System.out.println(cnt);
		}
	}

	private static void go(int n) {
		if (n <= 0) {
			cnt++;
			return;
		}

		if (n - 1 >= 0)
			go(n - 1);

		if (n - 2 >= 0)
			go(n - 2);

		if (n - 3 >= 0)
			go(n - 3);
	}
}

 

2차 코드

재귀함수에서 반복되는 부분을 for문으로 처리하였다.

import java.io.*;

public class Main {
	private static int cnt;

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

		for (int t = 0; t < T; t++) {
			int n = Integer.parseInt(br.readLine());
			cnt = 0;
			go(n);

			System.out.println(cnt);
		}
	}

	private static void go(int n) {
		if (n <= 0) {
			cnt++;
			return;
		}

		for (int i = 1; i <= 3; i++) {
			if (n - i >= 0)
				go(n - i);
		}
	}
}