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

📃 제출

import java.util.Scanner;

public class Main {
    static int[] arr = {1, 2, 3};
    static int N;
    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int tc = sc.nextInt();
        for (int i = 0; i < tc; i++) {
            N = sc.nextInt();
            answer = 0;
            dfs(0);
            System.out.println(answer);
        }
    }

    public static void dfs(int sum) {
        if (sum >= N) {
            if (sum == N) {
                answer++;
            }
            return;
        }

        for (int i : arr) {
            dfs(sum + i);
        }
    }
}

✏ 풀이

백트래킹 알고리즘을 사용하여 문제를 해결할 수 있었습니다. 백트래킹을 통해 가능한 모든 조합을 시도하였고 주어진 수 `N`과 같은 경우 카운트 하는 방식으로 문제를 해결할 수 있었습니다.

 

핵심 아이디어

• DFS
  • 매 호출마다 현재까지의 합계를 저장하였습니다.
  • 만약 현재 합계가 `N`보다 크다면 그 경우는 더 이상 진행할 필요가 없으므로 리턴합니다.
  • 현재 합계가 `N`과 같으면 유요한 조합을 찾았다고 판단하여 `answer`을 증가하였습니다.
• 백트래킹
  • 각각의 재귀 호출에서 1, 2, 3 중 하나를 더하여 새로운 합계를 생성합니다.
  • 재귀적으로 호출하여 모든 가능한 합계 조합을 만듭니다.
• 기저조건
  • 현재 합계가 N보다 크면 더 이상 탐색하지 않고 돌아갑니다.
  • 현재 합계가 정확히 N에 도달하면 가능한 조합으로 인정하여 카운트를 증가시킵니다.

 

기괴하다