2026.03.19 목

오늘 푼 문제

걷다보니신천역삼(Small)_14650

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class 걷다보니신천역삼Small_14650 {
    static int n;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        dfs(1, 1);
        dfs(1, 2);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }

    static void dfs(int depth, int sum) {
        if (depth == n) {
            if (sum % 3 == 0) {
                result++;
            }
            return;
        }

        for (int i = 0; i < 3; i++) {
            dfs(depth + 1, sum + i);
        }
    }
}

처음엔 맨 앞자리 제외하고 중복 순열인가? 했다가 2초에 9자리(맨앞자리 제외하면 8자리)길래 완전탐색 되겠다~ 해서 dfs 로 구현했다.

그리고 매번 문자열 -> 인트변환 -> 3으로 나눠보기 (귀찮다!!)

그래서 각 자리수의 합이 3의 배수인지 확인하는 방식을 택했다.