[백준] code.plus(브루트포스,JAVA)9095번, 1, 2, 3 더하기

문제 링크

9095번: 1, 2, 3 더하기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은 1, 2, 3을 사용하여 입력 값을 만드는 경우의 수를 구하는 것입니다.

저는 재귀를 사용해서 모든 경우의 수를 구해보았습니다.

 

예를 들어 입력값이 4이면

1 + 1 + 1 + 1 = 4(O)

1 + 1 + 1 + 2 = 5(X)

1 + 1 + 1 + 3 = 6(X)

 

1 + 1 + 2 = 4(O)

1 + 1 + 3 = 5(X)

 

1 + 2 + 1 = 4(O)

1 + 2 + 2 = 5(X)

1 + 2 + 3 = 6(X)

 

1 + 3 = 4(O)

 

2 + 1 + 1 = 4(O)

2 + 1 + 2 = 5(X)

2 + 1 + 3 = 6(X)

 

2 + 2 = 4(O)

2 + 3 = 5(X)

 

3 + 1 = 4(O)

3 + 2 = 5(X)

3 + 3 = 6(X)

 

결과적으로 7개가 나옵니다.

1 + 1 + 1 + 1 = 4(O)

1 + 1 + 2 = 4(O)

1 + 2 + 1 = 4(O)

1 + 3 = 4(O)

2 + 1 + 1 = 4(O)

2 + 2 = 4(O)

3 + 1 = 4(O)

 

문제에 해결알고리즘은

1. 입력값을 받습니다.

2. 재귀 함수를 이용하여 1, 2, 3의 경우의 수를 얻습니다.

3. 재귀 함수가 종료된 뒤 결과로 나온 모든 경우의 수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 1, 2, 3 더하기 경우의 수를 구하는 addingCount함수를 만들었습니다.
• BufferedWriter에 1, 2, 3 더하기 모든 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• addingCount는 재귀를 사용하여 모든 경우의 수를 구하였습니다.

 

결과 코드

import java.io.*;
public class Main{
	public static int count = 0;	//경우의 수 개수
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 함수 실행------
    	int N = Integer.parseInt(br.readLine());
    	for(int i=0;i<N;i++) {
    		int num = Integer.parseInt(br.readLine());
    		addingCount(num);
    		bw.write(count + "\n");		//결과 저장
    		count = 0;
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //------1, 2, 3 더하기로 만들 수 있는 경우의 수 구하는 함수------
    public static void addingCount(int cur) {
    	if(cur<=0) {		//현재 값이 음수일 때
    		if(cur==0)		//현재 값이 '0' 일 때
    			count++;
    		return;
    	}
        //1, 2, 3의 경우의 수 재귀
    	for(int i=1;i<=3;i++) {
    		addingCount(cur-i);
    	}
    }
}