*재귀함수* division

재귀 함수 문제입니다.

핵심

숫자가 작아지는 형태로 나타나야 한다. 재귀 함수를 만들 때, 매개변수로 값의 합과 인덱스 위치를 나타내는 값을 사용한다.

 

 

정답 코드

import java.util.Scanner;

public class Main {
    static int[] result;
    static int n;
    static int count;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        result = new int[n];
        division(0,0);
        System.out.println(count);
    }
    //현재까지 구한 합이 mysum
    //index번째 숫자를 결정할 차례 result[index]
    static void division(int mySum,int index) {
        if (mySum == n) {
            System.out.printf("%d",result[0]);
            for (int i = 1; i < index; i++) {
                System.out.printf("+%d", result[i]);
            }
            System.out.println();
            count++;
            return;
        }
        else {
            int myNumber;
            if (index==0) myNumber =n - 1;
            else myNumber = n-mySum;
            for (int i = myNumber; i >= 1; i--) {
                result[index] = i;
                if (index > 0 && result[index - 1] < result[index]) continue;

                division(mySum + i, index + 1);

            }

        }


    }
}

 

해설

재귀 함수 division을 만드는데 mySum, index는 각각 현재까지의 합과 인덱스 위치를 나타낸다.

따라서 기저 조건은 합이 우리가 원하는 수인 n과 같아질 때이다.

출력을 할 때, 숫자 사이에 +가 있는데, 이는 처음 값은 숫자만 출력하고 나머지는 +를 붙여서 출력하면 쉽게 해결된다.

index==0 일 때 myNumber = n-1을 한 이유는 index가 0일 때도 n-mySum을 myNumber에 넣게 되면,

첫 출력이 n 그 자체가 나오기 때문이다.

또한 내림차순으로 정렬하기 위해 현재 배열의 값이 그전 배열의 값보다 크면 continue 한다.

이후 mySum에 i를 더하고, index는 1을 올린 후 재귀 호출을 한다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.