[백준 알고리즘 / JAVA] 9095번 1, 2, 3 더하기

---

문제 정보

• 문제 링크: https://www.acmicpc.net/problem/9095
• 문제 번호: 9095번
• 문제 이름: 1, 2, 3 더하기
• 문제 난이도: 실버3
• 반복 학습 날짜
  • 2024.01.23 완료

9095번: 1, 2, 3 더하기

---

코드

import java.util.*;

public class Main {
    public static int count = 0; // 경우의 수를 세기 위한 변수

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // 테스트 케이스 개수 입력

        for(int i = 0; i < T; i++) {
            count = 0; // 각 테스트 케이스마다 경우의 수 초기화
            int N = scanner.nextInt(); // 목표 숫자 입력
            for(int j = 1; j <= 3; j++) {
                findWays(N, j); // 1, 2, 3을 시작으로 가능한 경우의 수 찾기
            }
            System.out.println(count); // 해당 테스트 케이스의 경우의 수 출력
        }
    }
    
    // N까지의 숫자를 만들 수 있는 경우의 수 찾는 재귀 함수
    public static void findWays(int N, int number) {
        if(N == number) { // 목표 숫자에 도달하면 경우의 수 증가
            count++;
        }
        
        if(N > number) { // 현재 숫자가 목표 숫자보다 작을 때
            for(int i = 1; i <= 3; i++) {
                int sumNumber = number + i; // 현재 숫자에 1, 2, 3을 더한 값
                findWays(N, sumNumber); // 더한 값을 다시 함수에 전달하여 경우의 수 찾기
            }
        }
    }
}

---

풀이

Step1: 재귀 함수를 사용하여, 합이 N이 되는 개수 찾기

// N까지의 숫자를 만들 수 있는 경우의 수 찾는 재귀 함수
public static void findWays(int N, int number) {
    if(N == number) { // 목표 숫자에 도달하면 경우의 수 증가
        count++;
    }

    if(N > number) { // 현재 숫자가 목표 숫자보다 작을 때
        for(int i = 1; i <= 3; i++) {
            int sumNumber = number + i; // 현재 숫자에 1, 2, 3을 더한 값
            findWays(N, sumNumber); // 더한 값을 다시 함수에 전달하여 경우의 수 찾기
        }
    }
}

1. "findWays"는 N까지의 숫자를 만들 수 있는 경우의 수를 찾는 함수로 첫 번째 조건문에서 목표 숫자와 현재 숫자가 같을 경우 "count"변수를 증가시킵니다.
2. 현재 숫자가 목표하는 숫자보다 작을 때 경우의 수(1, 2, 3 중 하나)를 더한 값을 함수에 전달하여 재귀호출합니다.