[백준] 22251: 빌런 호석 - JAVA

10 Oct 2023 in Algorithm on 구현

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

풀이

디지털 숫자의 눈금들을 반전시켜서 다른 숫자를 만들 수 있다.

다른 숫자가 되려면 몇 개를 반전시켜야 하는지 이차원배열 arr에 저장해놓고 시작했다.

dfs탐색을 통해 숫자 X를 일의자리부터 앞으로 가면서 바꿔줬다.

반전한 개수 누적하고 만들어진 숫자를 저장하면서 숫자가 N보다 크거나 반전 횟수가 P보다 크면 성립하지 않는 것이므로 return해주었다.

K자리 수까지 갔을 때 만족하면 result에 1을 더해주었다.

숫자가 0이 되는 경우를 제외했고, 현재 숫자와 같으면 안되므로 result에 -1해주었다.

---

메모리: 14292KB

시간: 196ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {
    static int[][] arr = {
            { 0, 4, 3, 3, 4, 3, 2, 3, 1, 2 },
            { 4, 0, 5, 3, 2, 5, 6, 1, 5, 4 },
            { 3, 5, 0, 2, 5, 4, 3, 4, 2, 3 },
            { 3, 3, 2, 0, 3, 2, 3, 2, 2, 1 },
            { 4, 2, 5, 3, 0, 3, 4, 3, 3, 2 },
            { 3, 5, 4, 2, 3, 0, 1, 4, 2, 1 },
            { 2, 6, 3, 3, 4, 1, 0, 5, 1, 2 },
            { 3, 1, 4, 2, 3, 4, 5, 0, 4, 3 },
            { 1, 5, 2, 2, 3, 2, 1, 4, 0, 1 },
            { 2, 4, 3, 1, 2, 1, 2, 3, 1, 0 }
    };

    static int N, K, P, X, result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        result = 0;
        solve(0, 0, 0);

        System.out.println(result - 1);
    }

    private static void solve(int idx, int sum, int cnt) {
        if (cnt > P || sum > N) {
            return;
        }

        if (idx == K) {
            if (sum != 0) {
                result++;
            }
            return;
        }

        for (int i = 0; i < 10; i++) {
            solve(idx + 1, sum + i * (int) Math.pow(10, idx), cnt + arr[X / (int) Math.pow(10, idx) % 10][i]);
        }
    }

}