[Baekjoon] 백준 9095번 1, 2, 3 더하기- Java

DP를 연습하면 좋을 거 같아서 백준 알고리즘을 풀게 되었습니다. 

다만 제출할 때 템플릿이 어디있는지 좀 헤맸어요 -.-

 

 

9095번 풀이 >

숫자 N에 대해서 1, 2, 3을 덧셈으로 표현할 수 있는 경우의 수의 갯수를 출력하는 문제.

 

import java.util.Scanner;

public class Main {
	static int count = 0;
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int test = scan.nextInt();
		
		for(int i = 0; i<test; i++) {
			count = 0;
			int target = scan.nextInt();
			dfs(target, 0);
			System.out.println(count);
		}
		
		
	}
	
	public static void dfs(int target, int n) {
		if(target < n)
			return;
		
		if(target == n) {
			count++;
			return;
		}
		
		else {
			dfs(target, n+1);		//1을 더했을 때
			dfs(target, n+2);		//2를 더했을 때
			dfs(target, n+3);		//3을 더했을 때
			
		}
	}

}

 

저는 dfs형식으로 했습니다. 요새 대부분의 문제는 거의 dfs로 푸는거 같아요

 

각각 현재 숫자에 1을 더했을 때, 2를 더했을 때, 3을 더했을 때 경우로 재귀로 호출하여 풀었습니다.