백준 12869번 : 뮤탈리스크 | JAVA

골드 4

 

📌 알고리즘 선택

이 문제는 빼지는 수도 3개, 빼는 숫자도 3개라 동전 문제보다 더 복잡하게 느껴졌던 문제였다.

BFS를 이용하여 사용한 공격 패턴에 따라 SCV 값들을 감소시켜며 공격 최소 횟수를 구하고, 

DP를 이용하여 감소된 SCV 값들을 기억하여 중복 연산 횟수를 줄였다.

 

---

`📌 풀이

1️⃣ scv의 수가 3개가 되도록 한다.

그래서 N이 1이나 2일 경우에는 scv의 수가 총 3개가 되도록 0을 채워준다.

 

2️⃣ visited[][][]의 3차원 배열을 통해 scv의 변화를 기록한다.

만약, visited[i][j][k] = 1일 경우, 0번 이상의 공격을 통해 (i, j, k)에 도달했다는 것을 의미한다.

이미 도달한 배열에 대해서는 다시 연산할 필요가 없으므로 연산을 멈춘다.

 

3️⃣ (i, j, k)와 (i, k, j)는 같은 작업이기 때문에,

visited[][][]의 3차원 배열 인덱스의 값들에 대해서는 반드시 정렬하여 방문 처리해야 한다.

정렬은 내림차순으로 해주었다.

 

4️⃣ 한 번의 공격에 대해서  9, 3, 1 만큼 3개의 scv에 공격을 할 수 있으므로, 총 6개의 공격 패턴이 존재한다.

그에 따라 6개의 재귀함수가 필요하다.

 

5️⃣ 3개의 scv에 대해서 모두 0 이하가 되면 종료한다.

 

---

📌 코드

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

public class Main {

    static int N;
    static ArrayList<Integer> scv;
    static int[][][] visited;
    static int result = Integer.MAX_VALUE;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // SCV의 수

        scv = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++)
            scv.add(Integer.parseInt(st.nextToken()));

        for(int i = N; i < 3; i++)
            scv.add(0);

        visited = new int[61][61][61];
        cal(scv.get(0), scv.get(1), scv.get(2), 0);

        System.out.println(result);

    }

    public static void cal(int a, int b, int c, int cnt) {

        a = Math.max(0, a);
        b = Math.max(0, b);
        c = Math.max(0, c);

        int max = Math.max(Math.max(a, b), c);
        int min = Math.min(Math.min(a, b), c);
        int mid = a + b + c - max - min;
        a = max;
        b = mid;
        c = min;

        if(a <= 0 && b <= 0 && c <= 0) {
            result = Math.min(cnt, result);
            return;
        }

        if(visited[a][b][c] == 1)
            return;
        else
            visited[a][b][c] = 1;

        if(result < cnt)
            return;

        cal(a-9, b-3, c-1, cnt+1);
        cal(a-9, b-1, c-3, cnt+1);
        cal(a-3, b-9, c-1, cnt+1);
        cal(a-3, b-1, c-9, cnt+1);
        cal(a-1, b-9, c-3, cnt+1);
        cal(a-1, b-3, c-9, cnt+1);

        return;

    }

}

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

12869번: 뮤탈리스크