[알고리즘 문제] division

import java.util.*;

public class Main {

    static int count = 0; // 출력할 수 있는 경우의 수
    static int num; // 입력받을 정수
    static String result = ""; // 결과를 표시할 문자열
    static Stack<Integer> stack = new Stack<>(); // num을 출력할 수 있는 조합

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        num = sc.nextInt();

        divisionSum(num - 1, 0);
        System.out.println(count);

    }

    static void divisionSum(int n, int sum) {
        if (sum == num) { 
            count++;
            for (int i : stack) {
                result += ("+" + i);
            }
            System.out.print(result.substring(1, result.length()));
            System.out.println();
            result = "";
        } else {
            for (int j = n; j >= 1; j--) {
                if (sum + j <= num) { 
                    sum += j; 
                    stack.push(j); 
                    divisionSum(j, sum); 
                    sum -= j; 
                    stack.pop(); 
                }
            }
        }
    }
}

문제는 자연수n을 입력받아 이를 n보다 작은 숫자들의 합으로 나타내는 방법을 모두 출력하는 프로그램이다.

예를들어 5의 경우 4+1 / 3+1+1/ 2+2+1/ 2+1+1+1/ 1+1+1+1+1으로 출력할 수 있다.

 

아이디어는 조합할 수 있는 숫자의 합인 sum에 입력받은 정수 n-1~1사이의 값 j를 더해가면서 sum+j <= num의 조건을 만족하는 모든 j를 스택에 저장하고, 만약 더해진 값이 입력받은 정수와 같다면 stack에 저장되어 있던 j값을 모두 출력한다.

 

일단 재귀함수가 어떻게 동작하는지 그림으로 살펴보겠다. divisionSum함수의 첫번째 인자는 n, 두번쨰 인자는 sum이다. 

 

먼저 main함수에서 divisionSum(4,0)이 호출이 된다. 첫번째로 if(sum==num)~에서 현재 sum=0, num=4이기 때문에 else문에 걸리게 된다. 위의 사진은 for문이 처음 실행됐을때 환경이다. for문의 if문에서 sum(0) + j(4) <= 5를 만족한다. 이 말은 j로 n보다 작은 숫자의 합을 표현할 수 있다는 말이다. sum에 j 값을 더해주고, stack에도 넣어준다. 여기서 스택은 n보다 작은 숫자들의 합을 표시하기 위해 사용한다. 

그리고 division(j,sum)을 다시 호출한다.

 

두번째 재귀함수. 첫번쨰 divisionSum이랑 완전히 다른 환경을 가진다. 그 말은 static변수를 제외하고 j,sum은 첫번째 divisionSum의 j,sum과 다른 값을 가진다. 두번째 재귀함수가 실행되면 역시 if문을 검사한다.현재 sum=4이고, num5이기 때문에 else문이 실행된다. else의 for문이 실행되고 sum(4) + j(4) 는 num(5)보다 크기 때문에 j값을 --한다. j=3,2인 경우 모두 지나치고 j=1인 경우 조건이 참이 된다. 그 말은 즉, sum에 j값을 더하면 num(5)가 된다는 말이다. 기존에 sum에는 4가 들어있었고 1을 더하면 5. 남은 녀석을 찾았기 때문에 sum에 더해주고 스택에도 넣는다. 그러고 다시 division(1,5)를 실행한다.

 

세번째 재귀함수. 먼저 조건을 검사하면 sum과 num값이 모두 5이기 때문에 첫번째 if문에 걸린다. 그리고 스택에 있는 값을 모두 출력한다. 밑에 substring하고 이런 것들은 출력조건에 맞추기 위해서 그런것이고 요점은  "자연수n을 입력받아 이를 n보다 작은 숫자들의 합으로 나타내는 방법" 중 하나를 찾았기 때문에 출력해준다는 것이다. 

 

 

이제 출력하면 세번째 재귀함수는 종료되었기 때문에 다시 세번째 재귀함수를 호출한 곳(두번째 재귀함수의 for문)으로 이동한다.

이제 두번째 재귀함수의 환경에서 이제 1의 경우는 출력해주었기 때문에 sum-=i를 한다. 여기서 sum=5, j=1이다. 그리고 stack에서도 pop해준다. 그러곤 다시 for문을 진행한다. 현재 j=1이기 때문에 stack.pop()을 하고 두번째 for문을 종료된다. 이제 다시 두번째 재귀함수를 호출한 곳(첫번째 divisionSum)으로 이동한다. 거기서 다시 for문을 돌면서 j값을 바꿔주고 위의 과정을 반복한다.

 

정리하면 2중,3중 for문이 동작하는 것과 같은 방식으로 동작한다. 처음에 지금까지 더한 값이 n이라면 더이상 더할 필요가 없기 때문에 그냥 출력해준다. 그렇지 않다면 for문을 돌면서 sum+j값이 n을 넘지 않는다면(오케이 j값은 들어갈 수 있겠군) sum에 j를 더하고 다시 재귀함수를 실행시켜준다. 만약 sum=num이라면 스택의 값들을 출력하고 해당 재귀함수를 호출했던 곳으로 돌아가서 다시 for문을 반복한다.