알고리즘 풀이 - 백준 9095(1, 2, 3 더하기, 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

이 문제는 1,2,3의 합으로 N을 나타내는 경우의 수를 출력하는 문제이다.
여기에서 DP로 푸는 방법을 설명한 바 있다. 이번에는 완전 탐색(재귀)를 이용하여 해결해본다.

 

 

2. 풀이

 

1, 2, 3을 모두 더하는 경우의 수를 완전 탐색으로 찾아보자.

찾은 후 그 결과가 현재 구하고자 하는 N의 값과 일치한다면 그 경우는 성공적인 것이며, 이외의 경우는 추가 연산이 필요하거나 실패한 경우이다.

 

즉, 이 내용을 재귀 함수로 구현할 수 있다. 재귀는 현재 함수의 상태를 지속적으로 넘김으로써 구하고자 하는 조건에 일치 시 탈출 조건을 만들어 전체 결과를 구하는 방법이다.

 

여기서 실패한 경우란, 만들고자 하는 숫자가 N일 때, 현재 재귀 함수로 만든 합의 결과(함수의 상태)가 N보다 크다면 실패인 것이다.

또한 성공한 경우는 위 합의 결과가 N과 같은 경우이다.

 

즉, 우리는 위의 경우에서 2가지 탈출 조건을 만들 수 있게 되었다. N보다 큰 상태인 경우, N과 같은 상태인 경우!

각각의 경우를 하나의 성공 / 실패의 경우의 수라고 볼 수 있다. 이 문제는 전체 경우의 수를 구하는 문제이므로 성공 시에만 전체 경우의 수에 +1을 하도록 반환한다면 그 결과를 구할 수 있다!

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        
        for(int i=0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            int ans = solve(0, n);
            
            bw.write(String.valueOf(ans));
            bw.write("\n");
        }
        
        bw.flush();
        br.close();
    }
    
    // n을 만드는 경우의 수를 구하는 재귀 문제
    // sum은 현재 까지의 합의 상태를 나타냄!
    private static int solve(int sum, int n){
    
        // 불가능한 경우 0 반환
        if(sum > n) return 0;
        
        // 가능 시 1 반환
        if(sum == n) return 1;
        
        // 현재의 재귀 함수 상태에서 이후에 가능한 경우의 수를 모두 구한 뒤 반환!
        int curr = 0;
        for(int i=1; i <= 3; i++){
            curr += solve(sum+i, n);
        }
        return curr;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.