BOJ_9095_1,2,3 더하기

문제는 다음과 같다.

재귀 함수를 이용해서 풀어보려한다.

본 문제에서 중요한 핵심은 아래와 같은 함수를 만들어내는 것이다.

---

private static int solution(int count, int sum, int goal) {

if (sum > goal)

return 0;

if (sum == goal)

return 1; // 바로 같을 경우는 1 출력 (1회)

int ans = 0;

//System.out.println(count + " / " + sum + " / " + goal);

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

// 1,2,3 으로만 값을 만들어 내야 하므로

ans += solution(count + 1, sum + i, goal);

/*

* 1,2,3 으로 값을 구할 때 카운트는 하나씩 증가하고 그 합은 1로 구할때와 2로 구할때 3으로 구할 때 각 단계별로 1씩 추가로 더

* 증가하게 됩니다.

*/

}

return ans;

}

---

재귀 함수로 쓰일 때 다음 n의 값이 오는 경우를 따지면 ( 1<= n && n<=3)

다음 n의 값으로 1이 오는 경우, count는 하나 증가하고 sum은 1 증가합니다.

다음 n의 값으로 2가 오는 경우, count는 하나 증가하고 sum은 2 증가합니다.

다음 n의 값으로 3이 오는 경우, count는 하나 증가하고 sum은 3 증가합니다.

숫자 count개로 합 sum을 만드는 경우이기 때문에 가능한 행동입니다. 

따라서 다음 함수에서 1,2,3의 합으로 값을 구하는 것이기 때문에 반복문은 1부터 3까지 돌도록하고, 그 안에서

재귀함수를 불러준다. (함수호출)

그리고 한 가지 빼먹은 것이 있는데, 종료 조건에 집중해야 한다.

모든 합은 goal을 넘어서는 안된다.

그렇기 때문에 sum > goal 일 경우 0을 반환하고, 

합이 goal과 같을 경우는 한 번에 찾은 것이기 때문에 1을 반환하도록 한다.

전체 코드는 아래와 같다.

---

import java.util.Scanner;

public class 원투쓰리더하기 {

private static Scanner scanner;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

int T = scanner.nextInt(); // 테스트 케이스

while (T-- > 0) {

int input = scanner.nextInt();

int ans = solution(0, 0, input);

// System.out.println(ans);

}

}

private static int solution(int count, int sum, int goal) {

if (sum > goal)

return 0;

if (sum == goal)

return 1; // 바로 같을 경우는 1 출력 (1회)

int ans = 0;

//System.out.println(count + " / " + sum + " / " + goal);

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

// 1,2,3 으로만 값을 만들어 내야 하므로

ans += solution(count + 1, sum + i, goal);

/*

* 1,2,3 으로 값을 구할 때 카운트는 하나씩 증가하고 그 합은 1로 구할때와 2로 구할때 3으로 구할 때 각 단계별로 1씩 추가로 더

* 증가하게 됩니다.

*/

}

return ans;

}

}

---