[Java] 백준 풀기 14650 - 걷다보니 신천역 삼 (Small)

자바 백준 14650번

실버 2

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

14650번: 걷다보니 신천역 삼 (Small)

 

 

 

 

 

문제 보기

분류: 수학, 다이나믹 프로그래밍, 브루트포스 알고리즘, 정수론

 

 

 

 

 

문제 풀기

재귀 함수를 사용하는 방법으로 문제를 해결한다.

 

첫째 숫자는 0이 불가능하므로 1, 2를 각각 시작 숫자로 하여 뒤에 0, 1, 2를 붙여나간다. N을 하나씩 줄여나가며..

재귀 함수를 돌때마다 N은 1씩 줄어들고 N이 1이 되었을 때 생성된 숫자가 3으로 나누어 지는지 판단하여 카운트를 한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        sc.close();
        
        // 0으로 시작하는 수는 만들 수 없으므로 첫 번째 자리는 1 또는 2만 가능
        long count = countValidMultiples(N, 1) + countValidMultiples(N, 2);
        
        System.out.println(count);
    }

    // 재귀 함수를 사용하여 가능한 N자리 3의 배수를 생성하고 세는 함수
    private static long countValidMultiples(int N, int currentNumber) {
        if (N == 1) {
            // 마지막 자리에 도달한 경우 3의 배수인지 확인하고 3의 배수면 1을 반환, 아니면 0 반환
            return (currentNumber % 3 == 0) ? 1 : 0;
        }
        
        long totalCount = 0;
        // 현재 숫자 뒤에 0, 1, 2를 붙여가며 재귀 호출
        for (int nextDigit = 0; nextDigit <= 2; nextDigit++) {
            int nextNumber = currentNumber * 10 + nextDigit;
            totalCount += countValidMultiples(N - 1, nextNumber);
        }
        
        return totalCount;
    }
}