[백준 알고리즘] 9095번 1, 2, 3 더하기

백준 알고리즘

1, 2, 3 더하기 (9095번)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	26598	16912	11563	62.224%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1

• 1+1+2

• 1+2+1

• 2+1+1

• 2+2

• 1+3

• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

해당 문제를 풀기 위해서 1, 2, 3 으로 각각 더했을때의 다음 경우를 탐색해나가며, 최종적으로 원하는 값이 출력되었을때 연산 결과를 +1 해주는 방식으로 풀 수 있다.

+1, +2, +3의 각각의 경우에 대해서 모두 재귀함수를 호출시키고 타겟값을 넘을경우에는 함수를 종료시켜주고, 일치하는 경우에 출력값에 +1을 해주었다.

또한 각 계산 결과값을 N회 반복해야하므로 다음번 연산에 사용되기 위해 기존에 사용된 ans 변수를 0으로 초기화 시켜주었다.

import java.util.Scanner;
​
public class Question9095 {
​
    static int N;
    static int goal;
    static int ans = 0;
​
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
​
        N = sc.nextInt();
        for(int i=0;i<N;i++){
            goal = sc.nextInt();
            solve(0, goal);
            System.out.println(ans);
            ans = 0;
        }
    }
​
    public static void solve(int sum, int goal) {
        if(sum==goal){
            ans++;
            return;
        }
        if(sum>goal) return;
​
        solve(sum+1, goal);
        solve(sum+2, goal);
        solve(sum+3, goal);
    }
}
​