[백준/Java] 9095 1, 2, 3 더하기* (feat. 브루트포스/완전탐색)

문제

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

# 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

n은 양수이며 11보다 작다.

# 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

 

---

 

 

 

이전 포스팅에서 다이나믹 프로그래밍을 사용해서 해결했는데,

스터디를 진행하면서 브루트 포스(재귀)로 푸는 방법을 습득하게 되어서

그 방식에 대해서도 따로 정리해두려 한다 ! 🎃

 

우선, 재귀란?

현재 함수의 상태를 지속적으로 넘김으로써 구하고자 하는 조건에 일치 시

"탈출조건"을 만들어 전체 결과를 구하는 방법이다.

 

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

찾은 후 그 결과가 현재 구하고자 하는 N의 값과 일치한다면 그 경우는 성공적인 것이며,

이외의 경우는 추가 연산이 필요하거나 실패한 경우이다.

 

여기서 실패한 경우란, 현재 재귀 함수로 만든 합의 결과(함수의 상태)가 N보다 클 때이며

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

 

=> 그래서 우리는 N과 큰 경우, N과 같은 상태 인 2가지 탈출조건을 만들 수 있다.

각가의 경우를 하나의 성공/실패의 경우의 수라고 볼 수 있다.

이 문제는 전체 경우의 수를 구하는 문제이므로 성공 시에만 전체 경우의 수에 +1 하도록

반환한다면 그 결과를 구할 수 있다.

 

 

풀이

import java.io.*;

public class Main {
	public static int countSum(int n, int cur) {
		if(cur >= n) {
			if(cur == n) return 1;
			return 0;
		}

		int result = 0;
		for(int i = 1; i <= 3; i++)
			result += countSum(n, cur + i);
		
		return result;
	}

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		while(n-- != 0)
			System.out.println(countSum(Integer.parseInt(br.readLine()), 0));
	}
}

 

** 아직 확실히 이해 가지 않는 부분은

왜? for 문을 3번만 도는 것인가에 대해서이다 . .

1, 2, 3 <- 이렇게 세가지 경우의 수가 주어지기 때문인걸까 ? . .

더 고민해봐야겠다 . .

 

 

© 참고

https://www.acmicpc.net/problem/9095

https://hongjw1938.tistory.com/106

https://enhjh.tistory.com/57

9095번: 1, 2, 3 더하기