[Java] 백준 22251번 : 빌런 호석

문제

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

22251번: 빌런 호석

 

풀이 과정

각 수마다 변경될 때 반전이 필요한 횟수를 arr배열에 저장했고, 이 코드는 미리 짜서 돌린후 대입해서 실제 코드에서는 넣지 않았다. 고정적인 값이라서 굳이 계속 돌릴 필요가 없다고 판단했다.

 

DFS를 통해서, 모든 경우의 수를 탐색한다. 여기서 (자리수, 10^(자리수), 현재까지 수, 반전시킨 횟수)를 인자로 넣어서 반전 시킨 횟수도 최대 횟수를 넘지않고, 현재 수가 N층을 넘지 않으면 통과시킨다.

이때 K자리까지 다 탐색했으면 결과+1을 하고 마지막엔 -1을 해서 자기자신은 제외시킨다. 빠트린 점은 0층인 경우는 없기 때문에 이것도 고려해서 제외시켜주면 된다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int result = 0, N, P, K, X;
    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}
    };

    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());//N층까지
        K = Integer.parseInt(st.nextToken());//자리수 <= 6
        P = Integer.parseInt(st.nextToken());//최대 반전 수
        X = Integer.parseInt(st.nextToken());//현재 층

        solve(0, 1, 0, 0);
        System.out.println(result - 1);
    }

    public static void solve(int idx, int temp, int su, int flipCnt){
        if(flipCnt > P || su > N) return;//최대 반전 수 넘으면 return
        if(idx == K){
            if(su!=0) result++;
            return;
        }

        for(int i=0; i<=9; i++){
            solve(idx+1, temp*10, i*temp + su, flipCnt + arr[X/temp%10][i]);
        }
    }
}

 

결과