백준 9095 - 1,2,3 더하기 (재귀)

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b9095_123%EB%8D%94%ED%95%98%EA%B8%B0_%EC%9E%AC%EA%B7%80.java

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

나에겐 재귀가 많이 어렵고 약한 부분이기 때문에 앞서 푼 문제와 똑같은 문제를 재귀로 풀어보았다.

재귀라는 것은 코드자체가 어떻게 동작하는지 하나하나 알아볼려면 어려운 것 같고, 코드의 동작원리는 함수의 안으로 들어갔다가 나오는 것이라는 것만 기억해두고 한 문제에 대한 모든 경우의 수를 찾는 것이 중요한 것 같다.

이 문제에서도 경우의 수를 모두 찾아줄 수 있었다.

 

찾을 수 있는 경우의 수:

1. 기존에 더해준 것 뒤에 1을 더한다.

2. 기존에 더해준 것 뒤에 2를 더한다.

3. 기존에 더해준 것 뒤에 3을 더한다.

 

여기에서 전체 합이 정수 n과 같으면 방법의 수에 1을 추가해주고 리턴해주면 되고, n을 넘으면 그냥 재귀를 빠져나오도록 리턴해주면 된다.

이 문제를 위한 재귀함수의 이름을 gogo라고 지어주고, 다음과 같이 구현했다.

 

//
//  Created by MinSeo on 2021/02/20.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class b9095_123더하기_재귀 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int answer=0;
    static int n=0;
    static void gogo(int sum) {
        if(sum==n) { 
            ++answer;
            return;
        }
        else if(sum>n)
            return;
        //기존에 더해준 것 뒤에 1을 더할 때
        gogo(sum+1);
        //재귀를 빠져나오면 sum+1에서 sum으로 나오게되고, sum에 다시 2를 더해준다.
        gogo(sum+2);
        //다시 재귀를 빠져나온 sum에 3을 더한다. sum이 n과 같거나 넘을 때 까지 반복.
        gogo(sum+3);
    }
    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        while(t-->0) {
            n = Integer.parseInt(br.readLine());
            gogo(0);
            bw.write(answer+"\n");
            answer = 0;
        }
        bw.flush();
    }
}