[필수 문제] division

1. 문제

임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우,

4
= 3+1
= 2+2
= 2+1+1
= 1+1+1+1

위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다.

2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2

자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오.

---

입력

첫 줄에 2 이상 20 이하의 자연수 n이 주어진다.

출력

첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 큰 식이 먼저 출력되도록 한다. 숫자와 더하기 사이에는 공백이 없다. 그리고 마지막 줄에는 나누어진 자연수의 개수를 출력한다.

예제 입력

5

예제 출력

4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
6

 

 

 

2. 풀이

division은  단순하지만 생각해내기 어렵고 까다로운 문제다. 순서가 다르더라도 숫자의 구성이 같으면 중복으로 포함하기 때문에 일반적인 완전탐색으로는 접근하기 어렵다. 이 문제의 핵심은 중복을 제거하는 방법과 재귀적 접근이다.

division	idx	sum (i)	result[idx]	지금까지 배열의 합 (totalSum)
division(5, 0, 0)	0	4	4	4
division(5, 1, 4)	1	1	1	5
division(5, 2, 5)	4 + 1 출력, division(5, 1, 4) 종료
division(5, 1, 4)	종료
division(5, 0, 0)	0	3	3	3
division(5, 1, 3)	1	2	2	5
division(5, 1, 5)	3 + 2 출력, division(5, 1, 3) 종료
division(5, 1, 3)	1	1	1	4
division(5, 1, 4)	2	1	1	5
division(5, 2, 5)	3 + 1 + 1 출력, division(5, 1, 4) 종료

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int[] result;
    private static int count;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        result = new int[n];

        division(n, 0, 0);

        bw.write(count + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void division(int n, int idx, int totalSum) {
        if(totalSum == n) {
            System.out.print(result[0]);
            for(int i = 1; i < idx; i++) {
                System.out.print("+" + result[i]);
            }
            count++;
            System.out.println();
        } else {

            int sum = 0;
            if(idx == 0) sum = n-1; // 첫 인덱스일 경우
            else sum = n - totalSum; // 남은 합계

            for(int i = sum; i > 0; i--) {
                result[idx] = i; // 가장 큰 수 부터 배열 앞에 넣기

                // 가장 큰 수 부터 나와야 중복 제거 가능하다는 점을 이용
                // idx-1 인덱스를 만족하기 위해서는 idx가 0보다 커야함
                if(idx > 0 && result[idx] > result[idx-1]) continue;

                division(n, idx+1, totalSum+i);
            }
        }
    }

}