자바(Java) 알고리즘: 모든 적을 처치하는 최소 폭격 횟수 구하기

문제 소개

이 문제의 목표는 건물 내 여러 개의 방에 숨어 있는 폭력배들을 최소한의 폭격 횟수로 모두 처치하는 것입니다. 각 방은 1번부터 n번까지 번호가 붙어 있으며, 다음과 같은 규칙이 적용됩니다.

폭력배는 첫 번째 폭격으로 부상을 입고, 두 번째 폭격을 맞으면 사망합니다.
방이 폭격당하면 그 방의 폭력배들은 생존을 위해 가장 가까운 방, 즉 인접한 방으로 급히 대피합니다.

따라서 우리가 구해야 하는 것은 건물 안의 모든 폭력배를 완전히 제거하기 위해 필요한 최소 폭격 횟수와, 어떤 순서로 방을 폭격해야 하는지입니다.

예시를 통한 이해

예시 1: 방이 3개인 경우

입력 — 방의 개수 = 3

출력 — 필요한 총 폭격 횟수

4
2 1 3 2

설명 — 필요한 최소 폭탄 수는 4개입니다. 먼저 2번 방을 폭격하면, 폭력배들은 살아남기 위해 1번 또는 3번 방으로 도망갑니다. 이어서 1번 방을 폭격하면, 앞선 2번 방 폭격으로 이미 부상당했던 폭력배 중 일부가 사망하고, 1번 방에 숨어 있던 폭력배는 부상을 입은 뒤 가장 가까운 2번 방으로 대피합니다. 다음으로 3번 방을 폭격하면, 2번 방 폭격 당시 3번 방으로 피신해 있던 부상당한 폭력배들이 사망하고, 원래 3번 방에 있던 폭력배들은 가장 가까운 2번 방으로 대피합니다. 마지막으로 2번 방을 다시 폭격하면 1번 방과 3번 방에서 넘어온 부상당한 폭력배들이 모두 사망하며 임무가 완료됩니다.

예시 2: 방이 2개인 경우

입력 — 방의 개수 = 2

출력 — 필요한 총 폭격 횟수

3
2 1 2

설명 — 필요한 최소 폭탄 수는 3개입니다. 먼저 2번 방을 폭격하면 폭력배들이 1번 방으로 도망갑니다. 이후 1번 방을 폭격하면, 2번 방 폭격 때 부상당해 피신해 있던 폭력배들이 사망하고, 1번 방에 있던 폭력배들은 부상을 입은 채 가장 가까운 2번 방으로 대피합니다. 마지막으로 2번 방을 한 번 더 폭격하면 남아 있던 부상당한 폭력배들이 모두 처치되며 임무가 끝납니다.

문제 해결 접근 방식

위 프로그램에서 사용된 접근 방식은 다음과 같습니다.

먼저 사용자로부터 방의 개수(n)를 입력받습니다.
필요한 폭탄의 총 개수를 (n + n/2) 공식으로 계산하여 출력합니다.
건물의 모든 짝수 번호 방을 폭격하고 해당 순서를 출력합니다.
이어서 모든 홀수 번호 방을 폭격하고 순서를 출력합니다.
마지막으로 짝수 번호 방을 한 번 더 폭격하여 폭격 과정을 마무리하고 결과를 사용자에게 출력합니다.

이 전략이 성립하는 핵심 원리는 다음과 같습니다. 짝수 방 폭격 시 폭력배들은 인접한 홀수 방으로 대피하고, 홀수 방 폭격 시에는 반대로 짝수 방으로 밀려납니다. 이 과정에서 이미 부상당한 폭력배들이 상대방의 폭격에 맞아 자연스럽게 사망합니다. 마지막으로 짝수 방을 재차 폭격함으로써 홀수 방에서 짝수 방으로 피신한 부상자들까지 모두 정리할 수 있습니다.

자바 코드 예제

public class TP {
    public static void main(String[] args) {
        int n = 8;
        System.out.println("Total Bombings required");
        // 필요한 총 폭격 횟수 = n + n/2
        System.out.println(n + n / 2);
        // 1단계: 짝수 방 폭격
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
        // 2단계: 홀수 방 폭격
        for (int i = 1; i <= n; i += 2)
            System.out.print(i + " ");
        // 3단계: 짝수 방 재폭격
        for (int i = 2; i <= n; i += 2)
            System.out.print(i + " ");
    }
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Total Bombings required
12
2 4 6 8 1 3 5 7 2 4 6 8

방이 8개인 경우 총 12번의 폭격(짝수 4회 + 홀수 4회 + 짝수 4회)으로 모든 폭력배를 처치할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적이며, 폭격 순서만 잘 설계하면 방의 개수와 무관하게 일정한 패턴으로 문제를 해결할 수 있다는 점이 흥미롭습니다.