백준 9095 1, 2, 3 더하기 Java

2019년 4월에 동적 프로그래밍으로 풀었었던 1, 2, 3 더하기 문제이다. 

이 문제를 재귀 호출을 통한 완전 탐색으로 푸는 방법을 정리한 글이다.

 

동적 프로그래밍으로 푸는 방법을 모른다면 아래의 글을 보도록 하자.

https://dundung.tistory.com/9?category=744408

백준 9095 1, 2, 3 더하기 Java

나는 아직 재귀 함수를 잘 다루지 못한다.

연습을 통해 재귀 함수를 잘 다루려고 노력해야겠다..

 

이 문제는 n이 주어졌을 때 이 n을 1, 2, 3의 합으로 나타내는 경우의 수를 출력하는 문제이다.

int go(int sum, int n) 이라는 함수를 만들 것이다.

sum은 현재까지 더해진 값이고 n은 목푯값이다.

 

종료 조건부터 생각하면

sum이 n보다 커지면 종료해야 한다.

if(sum > n){

   return 0;

}

그리고 sum이 n과 같으면 1을 리턴한다.

if(sum == n){

   return 1;

}

마지막으로 모든 경우의 수를 다 돌 수 있도록 재귀 호출을 한다.

int now = 0;

for(int i=1; i <=3; i++){

    now += go(sum+i, n);

}

return now;

 

마지막 부분이 메소드의 핵심 부분인데

재귀 호출이 돌면서 모든 경우의 수를 다 돌아보게 된다.

n이 4라면

go(0, 4)를 처음에 호출하고

go(1, 4)을 그다음 바로 호출하고

1에서 또 가능한 경우의 수

1에서 1을 더했을 때, 2를 더했을 때, 3을 더했을 때

BFS처럼 모든 경우를 순차적으로 다 돌면서

더한 값과 n값이 일치하는 경우에만 1을 리턴하면서 now에 1씩 쌓이게 된다.

 

import java.util.Scanner;
 
public class Q9095_ver2 {
 
    static int go(int sum, int n) {
        if(sum > n)
            return 0;
        if(sum == n)
            return 1;
        int now = 0;
        for(int i=1; i<=3; i++) {
            now += go(sum+i, n);
        }
        return now;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int tc = scan.nextInt();
        
        while(tc-- > 0) {
            int n = scan.nextInt();
            System.out.println(go(0, n));
        }
    }
}