[백준][BOJ] 27958 사격 연습

문제

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

27958번: 사격 연습

 

 

문제 접근

• N의 개수가 적은것으로 보아 브루트포스나 백트렉킹 유형의 가능성이 높아보인다.
• 예시를 볼 때, 그리디, 또는 DP적으로 생각해보아도 무언가 딱히 규칙성이 있어보이진 않았다. 그래서 브루트포스 유형으로 생각을 하고 접근하였다.
• N이 최대 8까지 올라갈 수 있고, 사격 횟수 K는 최대 5번까지이다. 이때 동일한 레인에서 쏴도 상관없다라는 설명이 있으므로 동일한 레인에 K번 모두를 사격할 수도 있다.
• 그래서 모든 경우의 수를 구하기 위해서는 레인 수 N개가 존재할 때, 중복을 허용하면서 K개를 선택하는 경우의 수 즉 중복 순열의 경우의 수가 나온다. $ N^K $의 경우의 수가 존재하며 최대 $ 2^{15} $로 3만개 정도의 순열만 탐색하면 된다.
• 이후 구한 모든 중복순열 결과에 대해 문제에서 요구하는 구현을 구현한다. 필자는 처음엔 막구현해서 해결한 뒤, 객체를 사용해서 해당 조각이 총탄에 의해 파괴되서 나온 잔여 표적인지를 확인할 때 추가적인 boolean 배열을 사용하지 않도록 개선하였다.
• 만약 잔여 표적이 다시 파괴되어 또 잔여 표적이 생기면 어떻하냐는 생각을 할 수 있는데 그럴 일은 없다. 초기 체력 / 4로 생성되는 추가 표적이 2번 이상 나오기 위해서는 표적의 체력이 16이상이 되어야 하는데, 보너스 표적이 아닌 표적은 9 이하의 자연수이고, 보너스 표적은 추가 표적을 생성하지 않기 때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Node{
        int health;
        boolean isFragment;

        Node(int health){
            this.health = health;
            isFragment = false;
        }
    }
    static Node[][] board;
    static Node[][] tmpBoard;
    static ArrayList<ArrayList<Integer>> per;
    static int N;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int ans = -1;

        board = new Node[N][N];
        tmpBoard = new Node[N][N];

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++){
                board[i][j] = new Node(Integer.parseInt(st.nextToken()));
            }
        }

        int[] bullet = new int[K];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < K; i++){
            bullet[i] = Integer.parseInt(st.nextToken());
        }

        int[] line = new int[N];
        for (int i = 0; i < N; i++){
            line[i] = i;
        }
        int[] out = new int[K];

        boolean[] visited = new boolean[N];
        per = new ArrayList<>();

        getPermutation(line, N, K, 0, visited, out);

        for (ArrayList<Integer> element: per){
            init();
            int scoreSum = 0;
            int bulletIdx = 0;

            for (int shootingLine : element){
                for (int i = 0; i < N; i++){
                    if (tmpBoard[shootingLine][i].health == 0){
                        continue;
                    }

                    if (tmpBoard[shootingLine][i].health >= 10){
                        scoreSum += tmpBoard[shootingLine][i].health;
                        tmpBoard[shootingLine][i].health = 0;
                        break;
                    } else{
                        if (tmpBoard[shootingLine][i].health <= bullet[bulletIdx]){
                            if (tmpBoard[shootingLine][i].isFragment){
                                scoreSum += tmpBoard[shootingLine][i].health;
                            } else{
                                scoreSum += board[shootingLine][i].health;
                            }

                            for (int dir = 0; dir < 4; dir++){
                                int ny = shootingLine + dy[dir];
                                int nx = i + dx[dir];

                                if (ny < 0 || ny >= N || nx < 0 || nx >= N){
                                    continue;
                                }

                                if (tmpBoard[ny][nx].health == 0){
                                    if (!tmpBoard[shootingLine][i].isFragment && board[shootingLine][i].health / 4 != 0){
                                        tmpBoard[ny][nx].health = board[shootingLine][i].health / 4;
                                        tmpBoard[ny][nx].isFragment = true;
                                    } else{
                                        break;
                                    }
                                }
                            }

                            tmpBoard[shootingLine][i].health = 0;
                        } else{
                            tmpBoard[shootingLine][i].health -= bullet[bulletIdx];
                        }
                        break;
                    }
                }
                bulletIdx++;
            }

            ans = Math.max(ans, scoreSum);
        }

        System.out.println(ans);
    }

    public static void init(){
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                tmpBoard[i][j] = new Node(board[i][j].health);
            }
        }
    }

    public static void getPermutation(int[] arr, int N, int R, int depth, boolean[] visited, int[] out){
        if (depth == R){
            ArrayList<Integer> result = new ArrayList<>();
            for(int element: out){
                result.add(element);
            }

            per.add(result);
            return;
        }

        for (int i = 0; i < N; i++){
            out[depth] = arr[i];
            getPermutation(arr, N, R, depth + 1, visited, out);
            out[depth] = 0;
        }
    }
}

• 시간 복잡도는 대략적으로 $ O(N^K) $ 인데, 실질적인 연산 자체도 5천만이 넘어가지는 않는것으로 보인다.
• 경우의 수만 뽑는다면 나머지는 순수 구현 + 시뮬레이션이었던 문제였다.