[문제] 자연수의 분할

문제

 

소스코드

import java.util.Scanner;  

public class Division2 { 	 	
    private static int N; 	
    private static int cnt = 0; 	
    static int[] array = new int[20]; 	
    
    public static void main(String[] args) { 		
        Scanner sc = new Scanner(System.in); 		
        N = sc.nextInt(); 		
        division(N, 0, 0); 		
        System.out.println(cnt); 	
    } 	 	

    private static void division(int n, int sum, int index) { 		
        for(int x=n; x>0; x--){ 			
            if(index==0){ // 처음 시작 숫자 				
                array[index] = x-1; 				
                division(n-(x-1), x-1, index+1); 			
            } 			
            else{ // 그 외 				
                array[index] = x; 				
                if(x<=array[index-1]) // 현재 숫자가 이전 숫자보다 작거나 같을 경우만 					
                division(n-x, sum+x, index+1);	 			
            } 		
        }		 		
        if(N == sum){ 			
            print(index); 			
            System.out.println(); 		
        } 	
    }  	
    
    private static void print(int index) { 		
        cnt++; 		
        for(int i=0; i<index; i++){ 			
            System.out.print(array[i]); 			
            if(i!=index-1){ 				
            	System.out.print("+"); 			
            } 		
    	} 	
    }
    
}

 

풀이

 

개인적으로 정말 풀기 힘들었던 문제였다. ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

재귀함수는 처음부터 완벽하게 디자인 하지 않으면 제대로 된 결과 값을 보지 못하기 때문이다.

 

먼저 출력 예제를 간단히 보면 맨 앞에 나열된 숫자들은 아래로 내려올수록 작아지고, 오른쪽으로 나열된 숫자들은 앞의 숫자보다 같거나 작다는 것이다.

 

내가 짠 코드를 풀이해보자면 예를 들어 N에 값을 5로 받았다고 해보자 !

 

첫 번째, 자연수 5를 입력받는다. division(5, 0, 0) 를 호출한다. 이때 division(int n, int sum, int index)의 파라미터 값을 설명해보자면 n의 경우 앞으로 나열해야 할 남은 값, sum은 앞서 나열한 값들의 합, index는 결과 값을 넣을 배열의 인덱스를 의미한다.

 

두 번째, 

for문을 5만큼 반복한다.

if문의 경우는 첫 번째 수를 완성하고, else문의 경우 그 뒤에 나열된 수들을 완성한다고 보면 된다.

중요한 점은 앞에 나열된 수보다 뒤에 나열될 수가 커서는 안 되기 때문에 else문 안에 if문을 써서 이를 방지한다.

 

세 번째,

앞서 나열한 값들 의 합, 즉 sum이 처음 입력받은 N과 같아지면 print() 메소드를 통해 출력한다.

또한 cnt값을 증가시킨다.

 

네 번째,

cnt 값을 출력한다.

 

설명을 하고보니 무척 심플(?)하다. 하핳ㅎ.. ㅠ