[백준_12101번] 1, 2, 3 더하기 2

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

12101번: 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

 

이를 사전순으로 정렬하면 다음과 같이 된다.

 

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

 

[입력 조건]

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_12101 {
	static ArrayList<String> arr=new ArrayList<>();
	static int n,k,count=0;
	static boolean flag=false;
	static int[] choice;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		choice=new int[n];
		
		dfs(0,0);
		
		// k번째에 오는 식이 없다면 -1 출력
		if(!flag)
			System.out.println(-1);
	}
	
	static void dfs(int depth, int sum) {
		// 수의 누적 합이 n을 초과할 경우 넘어간다.
		if(sum>n)
			return;
		
		// 수의 누적 합이 n일 경우
		if(sum==n) {
			count++; // 갯수 증가
			
			// 합쳐서 n이 되는 식의 개수가 k번째라면
			if(count==k) {
				flag=true;
				// 식 출력
				for(int i=0;i<depth-1;i++) {
					System.out.print(choice[i]+"+");
				}
				System.out.print(choice[depth-1]);
			}
			return;
		}
		
		// 백트래킹
		for(int i=1;i<=3;i++) {
			choice[depth]=i; // depth 번째에 1~3 중 선택
			dfs(depth+1,sum+i); // 깊이를 1 증가시키고, 수의 합에 i를 더한 후 재귀호출
		}
	}
}

 

[고찰]

 이번 문제는 해결 방법이 다양한 것 같지만 위 코드는 백트래킹을 사용하여 해결한 방법이다. 재귀의 깊이를 늘려가며 1~3 숫자중 하나를 선택해 누적합이 n이 될때 재귀를 멈춰 n이 되는 수식의 개수를 count 해주면 된다. 이때 count 값이k가 될 경우는 k번째에 선택한 숫자들을 A+B... 형태의 수식으로 출력해주면 된다. 이때 백트래킹 함수는 매개변수로 재귀의 깊이와 수의 누적 합을 갖고있어야 한다. 수의 누적 합을 갖고있지 않으면 재귀를 멈출 조건이 없기 때문이다.