밍의 기록들😉

[문제] 자연수의 분할 본문

자료구조, 알고리즘/문제풀이

[문제] 자연수의 분할

민쓰 2018. 9. 4. 00:07

문제


소스코드

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 값을 출력한다.


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





'자료구조, 알고리즘 > 문제풀이' 카테고리의 다른 글

[문제] 웜바이러스 2606번  (0) 2018.09.05
[문제] 이진 패턴  (0) 2018.09.04
[문제] 자연수의 분할  (4) 2018.09.04
[문제] 단지번호 붙이기 2667번  (0) 2018.08.27
[문제] 분수 합 1735번  (0) 2018.08.16
[문제] 가로수 2485번  (0) 2018.08.16
4 Comments
댓글쓰기 폼