[백준] 1, 2, 3 더하기 (자바) (순열 알고리즘)

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

입력

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

출력

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

---

코드

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

public class Main {
	static int T, n, cnt;
	static int[] src = { 1, 2, 3 };
	static int[] tgt;

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

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

			for (int i = 1; i <= n; i++) {
				tgt = new int[i];
				perm(0);
			}

			System.out.println(cnt);
		}
	}

	static void perm(int tgtIdx) {
		if (tgtIdx == tgt.length) {
			int sum = 0;
			for (int i = 0; i < tgt.length; i++) {
				sum += tgt[i];
			}

			if (sum == n) {
				cnt++;
			}
			return;
		}

		for (int i = 0; i < src.length; i++) {
			tgt[tgtIdx] = src[i];
			perm(tgtIdx + 1);
		}
	}
}

 

풀이

지난번엔 1, 2, 3 더하기 문제를 DP로 풀어서 올렸었다. (dp를 이용한 풀이는 아래 글 참고) 

[백준] 9095번 1, 2, 3 더하기 (파이썬)

 

 

----

현재 순열 조합을 공부 중이라 순열을 이용한 방법으로도 풀어보았다! 

• 합을 나타낼 배열의 크기를 1부터 n까지 늘려가며
• {1, 2, 3} 세 숫자의 중복순열을 이용
• 만들어진 순열의 합이 n과 같아질 경우에만 cnt 수 증가 

위와 같이 해결하면 된다. 

 

dp와 순열 풀이의 제출 메모리와 시간