Java - 1, 2, 3 더하기

1. 문제

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
• 문제 출처) https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

2. 생각

 본 문제를 푸는 알고리즘은 다양하지만, Recursion의 연습을 위해 Recursion으로 풀도록 하겠다.

 

2.1. Recursion Thinking

 Recursion을 이용한 알고리즘은 다음과 같다.

• 합계(value) 값을 0으로 초기화한 뒤, 1부터 3까지 각각 더한다.
• if) 합계(value) 값이 입력 받은 값(num)보다 크면 "해당 구성 요소들의 합으로 입력 받은 값(num)를 표현할 수 없음"을 의미하기 때문에 Return하여 마무리.
• another if)  합계(value) 값이 입력 받은 값(num)과 일치하면 "이전까지의 구성 요소들의 합으로 입력 받은 값(num)를 표현할 수 있음"을 의미하기 때문에 Return하여 마무리.
• 위 두 조건을 모두 만족하지 않는다면, Recursion을 이용하여 위 조건을 만족할 때까지 반복

 

위 과정을 입력 받은 값(num)이 4일 때를 가정하고, 그림으로 표현하면 다음과 같다.

입력 받은 값이 4인 경우,  합으로 나타내는 방법의 수는 7가지이다. (그림 실력...ㅠㅠ)

 

2.2. Recursion code 구현

위 알고리즘을 바탕으로 코드를 간략하게 구현하면 다음과 같다.

int getCase(int num, int value)
    // ** Base case. 구성요소들의 합으로 표현 가능
    if(value == num)
    	return 1;
        
    // ** count = 합으로 나타내는 방법의 수
    int count = 0;
    // ** Recursion case
    for(int i=1; i<4; i++)
    	// ** 조건) 구성요소들의 합으로 표현 가능한 경우만 실행
    	if(value+i <= num)
    	    count += getCase(num, value+i);
            
    return count;

---

3. 풀이 및 코드 분석

import java.util.Scanner;

public class Main {
	static Scanner scan = new Scanner(System.in);
	public static void main(String[] args) {
		int number = getNumber();		
		int[] result = new int[number];
		
		for(int i=0; i<number; i++) {
			int data = scan.nextInt();
			int count = getCouple(data, 0);
			result[i] = count;
		}
		
		for(int i=0; i<number; i++) {
			System.out.printf("%d\n", result[i]);
		}
	}
	
	// *** Get number of data.
	private static int getNumber() {
		int input = 0;
		
		while(true) {
			input = scan.nextInt();
			
			if(input<=0)
				System.out.println("The number is less than 1.");
			else if(input>=11)
				System.out.println("The number is greater than or equal to 11.");
			else
				break;
		}
		
		return input;
	}
	
	// *** Find the couple of additions.
	private static int getCouple(int num, int value) {
		if(value==num) 
			return 1;
		
		int count = 0;
		for(int i=1; i<4; i++) {
			if(value+i<=num)
				count += getCouple(num, value+i);
		}		
		
		return count;
	}
}

 

입력 받은 값(num)의 합으로 나타내는 경우도 출력을 원할 경우)

package FindTheCoupleAdditions;

import java.util.Scanner;
import java.util.ArrayList;

public class FindTheCouple {
	static ArrayList<int[]> list = new ArrayList<>();
	static int number;
	
	public static void main(String[] args) {
		// ** Get data & initialization.
		number = getNumber();
		int[] couple = new int[number];
		
		// ** 1) Current total, 2) Current couple, 3) Current level
		findCouples(0, couple, 0);
		
		// ** Print list.
		printList();
	}
	
	// *** Get number.
	private static int getNumber() {
		Scanner scan = new Scanner(System.in);
		
		int input = 0;
		while(true) {
			System.out.print("Enter number: ");
			input = scan.nextInt();
			
			if(input<1)
				System.out.println("The number is less than or equal to 0");
			else 
				break;
		}
		
		return input;
	}
	
	// *** Find couple.
	private static void findCouples(int total, int[] couple, int level) {
		if(total==number) {
			// ** if, 그냥 저장하면 reference를 저장하는 것이기 때문에 문제 발생
			addList(couple);
			return;
		}
		
		for(int i=1; i<4; i++) 
			if(total+i<=number) {
				// ** if, 초기화를 안할 경우, 뒤에 Garbage value가 들어가서 문제 발생
				for(int j=level+1; j<number; j++)
					couple[j] = 0;
					
				couple[level] = i;
				findCouples(total+i, couple, level+1);
			}
	}
	
	// *** Add new couple to array list.
	private static void addList(int[] couple) { 
		int[] newCouple = new int[number];
		
		for(int i=0; i<number; i++)
			newCouple[i] = couple[i];
		
		list.add(newCouple);
	}
	
	// *** Print the array list.
	private static void printList() {
		System.out.printf("\nThe number of couple = %d.\n", list.size());
		
		for(int i=0; i<list.size(); i++) {
			System.out.printf("List[%d] = ", i+1);
	
			int index = 0;
			while(index<number && list.get(i)[index]!=0) {
				if(index==0)
					System.out.printf("{%d", list.get(i)[index]);
				else
					System.out.printf(" + %d", list.get(i)[index]);
				
				index++;
			}
			System.out.println("}");
		}
	}
}

Enter number: 4

The number of couple = 7.
List[1] = {1 + 1 + 1 + 1}
List[2] = {1 + 1 + 2}
List[3] = {1 + 2 + 1}
List[4] = {1 + 3}
List[5] = {2 + 1 + 1}
List[6] = {2 + 2}
List[7] = {3 + 1}

---

4. 메모

• 알고리즘의 아이디어는 대략적으로 생각해 내었지만, 코드 구현이 생각보다 오래 걸렸다.
  Recursion에 대한 연습이 필요하다고 생각한다.