[Baekjoon 14650 / Java / 실버2] 걷다보니 신천역 삼 (Small)

문제, 테스트 케이스

 

문제는 간단하다. 숫자 0, 1, 2만 사용해서 N자리 숫자를 만들고, 그 중에서 3의 배수가 몇 개인지 출력하면 된다.

수학적으로 풀면 간단할 거라고 생각했지만 난 백트래킹 방식으로 경우의 수들을 계산하여 풀었다.

 

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class 걷다보니_신천역_삼_Small_14650 {

    static int cnt = 0;

    static int N;

    public static void main(String[] args) throws Exception{

       

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력받기

        N = Integer.parseInt(br.readLine());

        // 백트래킹 진행

        backTracking(0, "");

        // 결과 출력

        System.out.println(cnt);

    }

    public static void backTracking(int depth, String num) {

        // 최대 깊이에 도달했을 경우

        if(depth == N) {

            // num이 3의 배수면 cnt += 1

            if((Integer.parseInt(num) % 3 == 0)) {

                cnt += 1;

            }

            return;

        }

        // 첫 번째 자리라면 1, 2만 넣기

        if(num.equals("")) {

            for(int i = 1; i < 3; i++) {

                backTracking(depth + 1, num + i);

            }

        }

        // 아니라면 0, 1, 2 넣기

        else {

            for(int i = 0; i < 3; i++) {

                backTracking(depth + 1, num + i);

            }

        }

    }

}

 

첫 번째 숫자가 0이면 안되기 때문에 그에 대한 조건을 걸어서 1, 2만 들어가도록 했다.

첫 번째 숫자가 아니라면 0, 1, 2 모두를 들어가게 했다.

 

문자열 형식으로 덧셈해서 숫자를 만든 후, N자리가 완성되었을 경우 3의 배수인지 검사해서 맞다면 cnt를 증가시켰다.