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을 더했을 때 경우로 재귀로 호출하여 풀었습니다.
'알고리즘 > 백준' 카테고리의 다른 글
[BaekJoon] 백준 2193 이친수 -Java (0) | 2020.05.17 |
---|---|
[BaekJoon] 백준 2579. 계단 오르기 - Java (0) | 2020.05.14 |
[BaekJoon] 백준 1932. 정수 삼각형- Java (0) | 2020.05.13 |
[BaekJoon] 백준 11726 2xn 타일링- Java (0) | 2020.05.05 |
[Baekjoon] 백준 1463번. 1로 만들기- Java (0) | 2020.05.05 |