백준 | 9095번. 1,2,3 더하기 - 백트래킹(DFS) 문풀

⬛ 백준 9095번. 1,2,3 더하기 - 백트래킹(DFS) 문풀

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

9095번: 1, 2, 3 더하기

문제

정수 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 = 3일때, 방법의 수가 4가지가 되는데 다음과 같은 경우다.
                  3= 1+1+1 =  1+2 =  2+1 =  3  (4가지) 

• 위의 예시에서 알 수 있듯, 1, 2 ,3을 중복 사용해도 상관없고 어쨋든 그 조합의 방법이 N이 되면 카운팅하면 되는 문제인 것이다.
• DFS로 깊이 탐색을 시도할 때 방문 체크할 필요없이 매번 1~3 의 값을 더해보면서 다음 깊이를 탐색한다.
• 쭉 탐색을 시도했을 때, sum값이 N을 넘어서버리면 더 탐색할 필요도 없으므로 리턴하고,sum값이 N과 같아진 경우에는 count++처리를 해주면 전체 방법의 수가 구해진다.

풀이 부연 설명 그림

• 예전에 DP로 풀어본 문제였는데, 이번에는 백트래킹으로 풀어봤다.

백준 | 9095번. 1, 2, 3 더하기 - DP 문제

---

💚 제출 코드

import java.util.Scanner;

/**
 * 백준 9095번. 1,2,3 더하기 - 백트래킹 문풀 
 * @author MYLG
 *
 */
public class Main {
	static int TC;
	static int N;
	static int count;
	//DFS
	static void DFS(int sum) {
		if(sum >= N) {
			if(sum == N) count++;
			//더 커진 경우는 탐색 불필요하므로 그냥 리턴
			return;
		}
		
		for(int i=1; i<=3; i++) {
			DFS(sum + i);//더 깊이 탐색 
		}
	}

	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		TC = kb.nextInt();
		
		for(int t=0; t<TC; t++) {
			N =kb.nextInt();
			count = 0;
			
			DFS(0);
			System.out.println(count);	
		}
	}
}