백준 1006 습격자 초라기 Java

ChoRong0824·2023년 5월 30일
0

Java

목록 보기
23/31
post-thumbnail

문제

링크 : https://www.acmicpc.net/problem/1006


접근 방법

먼저 습격자 초라기 문제에 대한 정보를 파악한 후에, 핵심 아이디어를 도출하고 이를 구현할 접근 방법을 설명합니다.

문제

우리 복리 팀은 둘레로 둘러싸인 길이 N인 선형 벽돌로 구성된 적의 요새를 습격했습니다. 각 벽돌은 부서질까지 일정 횟수의 공격을 받을 수 있습니다. 복리 팀은 2명이서 습격 계획을 세웠고, 한 사람의 공격력이 모두 다르습니다. 한 사람이 공격할 수 있는 벽돌 개수가 제한되어 있으며, 연속된 벽돌을 공격해 부수려 합니다.

두 명의 복리 팀은 순차적으로 이동하며, 각 이동 시 공격력과 그것을 적용할 벽돌 범위를 계획해야 합니다. 다만, 한 벽돌에 대한 공격횟수는 중복 계산되지 않아야 합니다. 최대한 많은 벽돌을 부수는 것이 목표입니다.

핵심 아이디어

이 문제의 핵심 아이디어는 동적 계획법(Dynamic Programming)입니다.
각 회차별 최선의 전략을 단계별로 최적화하면서 문제를 해결합니다.

접근 방법

  1. 벽돌의 내구도를 저장하는 int[] dp 배열을 생성합니다.
  2. 두 사람의 공격력을 각각 p1, p2라고 하면 이들 각각에 대해 모든 벽돌을 순회하면서 각 케이스의 최적 결과를 계산합니다.
  3. 모든 경우의 수를 계산하여 최대 벽돌 파괴 횟수를 추출합니다.
  4. 최종 결과를 출력합니다.

Code

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

public class Main {
    private static int rowCount, specialUnitCount;
    private static int[][] enemyCounts;

    private static int[] upperRowDP;
    private static int[] lowerRowDP;
    private static int[] combinedRowDP;

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

        int testCaseCount = Integer.parseInt(reader.readLine());

        for (int i = 0; i < testCaseCount; i++) {
            int minResult = Integer.MAX_VALUE;

            String[] input = reader.readLine().split(" ");

            rowCount = Integer.parseInt(input[0]);
            specialUnitCount = Integer.parseInt(input[1]);

            enemyCounts = new int[2][rowCount];

            for (int j = 0; j < 2; j++) {
                input = reader.readLine().split(" ");

                for (int k = 0; k < rowCount; k++) {
                    enemyCounts[j][k] = Integer.parseInt(input[k]);
                }
            }

            upperRowDP = new int[rowCount];
            lowerRowDP = new int[rowCount];
            combinedRowDP = new int[rowCount + 1];

            upperRowDP[0] = 1;
            lowerRowDP[0] = 1;
            combinedRowDP[0] = 0;

            solve(0);
            minResult = Math.min(minResult, combinedRowDP[rowCount]);

            if (rowCount > 1) {
                if (enemyCounts[0][0] + enemyCounts[0][rowCount - 1] <= specialUnitCount
                        && enemyCounts[1][0] + enemyCounts[1][rowCount - 1] <= specialUnitCount) {
                    upperRowDP[1] = 1;
                    lowerRowDP[1] = 1;
                    combinedRowDP[1] = 0;

                    solve(1);
                    minResult = Math.min(minResult, combinedRowDP[rowCount - 1] + 2);
                }

                if (enemyCounts[0][0] + enemyCounts[0][rowCount - 1] <= specialUnitCount) {
                    upperRowDP[1] = 2;
                    lowerRowDP[1] = enemyCounts[1][0] + enemyCounts[1][1] > specialUnitCount ? 2 : 1;
                    combinedRowDP[1] = 1;

                    solve(1);
                    minResult = Math.min(minResult, lowerRowDP[rowCount - 1] + 1);
                }

                if (enemyCounts[1][0] + enemyCounts[1][rowCount - 1] <= specialUnitCount) {
                    upperRowDP[1] = enemyCounts[0][0] + enemyCounts[0][1] > specialUnitCount ? 2 : 1;
                    lowerRowDP[1] = 2;
                    combinedRowDP[1] = 1;

                    solve(1);
                    minResult = Math.min(minResult, upperRowDP[rowCount - 1] + 1);
                }
            }

            System.out.println(minResult);
        }

        reader.close();
    }

    private static void solve(int startIndex) {
        for (int i = startIndex; i < rowCount; i++) {
            combinedRowDP[i + 1] = Math.min(upperRowDP[i] + 1, lowerRowDP[i] + 1);

            if (enemyCounts[0][i] + enemyCounts[1][i] <= specialUnitCount) {
                combinedRowDP[i + 1] = Math.min(combinedRowDP[i + 1], combinedRowDP[i] + 1);
            }

            if (i > 0 && enemyCounts[0][i - 1] + enemyCounts[0][i] <= specialUnitCount
                    && enemyCounts[1][i - 1] + enemyCounts[1][i] <= specialUnitCount) {
                combinedRowDP[i + 1] = Math.min(combinedRowDP[i + 1], combinedRowDP[i - 1] + 2);
            }

            if (i < rowCount - 1) {
                upperRowDP[i + 1] = combinedRowDP[i + 1] + 1;
                lowerRowDP[i + 1] = combinedRowDP[i + 1] + 1;

                if (enemyCounts[0][i] + enemyCounts[0][i + 1] <= specialUnitCount) {
                    upperRowDP[i + 1] = Math.min(upperRowDP[i + 1], lowerRowDP[i] + 1);
                }

                if (enemyCounts[1][i] + enemyCounts[1][i + 1] <= specialUnitCount) {
                    lowerRowDP[i + 1] = Math.min(lowerRowDP[i + 1], upperRowDP[i] + 1);
                }
            }
        }
    }
}

코드설명

이 코드는 임무를 완수하기 위해 건물을 세우는 최소 공격 횟수를 구하는 문제를 해결합니다. 주어진 테스트 케이스의 수만큼 반복을 수행하며 각 테스트 케이스 때마다 다음과 같은 프로세스를 거칩니다.

  1. 테스트 케이스를 얻고 행 개수(rowCount)와 특수 유닛 개수(specialUnitCount)를 입력 받습니다.
  2. 상단과 하단 적의 위치에 있는 적의 수를 각각의 배열(enemyCounts)에 저장합니다.
  3. 각 행의 상단(upperRowDP), 하단(lowerRowDP), 상단과 하단 모두(combinedRowDP)를 공격하는 최소 공격 횟수를 저장할 동적 프로그래밍 배열을 초기화합니다.
  4. solve(int startIndex) 함수를 호출하여 각 행에 대한 최소 공격 횟수를 계산하고 동적 프로그래밍 배열을 채웁니다.
  5. 계산된 최소 공격 횟수 중 가장 작은 값을 최종 결과로 출력합니다.

solve(int startIndex) 함수는 다음과 같은 접근 방식을 사용합니다:

  • 시작 인덱스부터 각 행에 대해 상단, 하단 또는 상단과 하단을 공격하는 경우를 확인하고, 공격 횟수를 동적 프로그래밍 배열에 저장합니다.

  • 각 행에 대해 가능한 최소 공격 횟수를 계산하기 위해 다양한 조건을 비교하고 최소값을 찾습니다.

  • 이를 통해, 이전 행에서의 최소 공격 횟수를 기반으로 현재 행에서의 최소 공격 횟수를 구할 수 있습니다.

  • 이해를 돕기 위한 몇 가지 주요 기능은 다음과 같습니다

  • 상단과 하단을 동시에 공격하기 위해서는 해당 행의 상단과 하단 적 유닛의 합이 specialUnitCount 보다 작거나 같아야 합니다.

  • 어떤 연속된 두 행에서 상단 또는 하단에서만 공격하는 것이 가능하려면 이 두 행의 상단 적 유닛 또는 하단 적 유닛의 합이 specialUnitCount보다 작거나 같아야 합니다.

코드는 자세한 계산을 실시하여 모든 가능한 경우를 탐색하고 동적 프로그래밍 배열을 갱신하여 최소 공격 횟수를 계산합니다. 결과적으로, combinedRowDP 배열의 마지막 요소에 최종 해답이 저장됩니다.


다시 말해, 코드에 사용된 접근법을 바탕

으로 문제 해결 전략을 설명하겠습니다.

문제의 목표는 건물을 지키기 위해 필요한 최소 공격 횟수를 계산하는 것입니다.
두 개의 각기 다른 정보가 주어지는데, 첫째는 건물 행의 수와 각 특수유닛이 공격할 수 있는 적 유닛 수, 그리고 상하단에 위치한 적 유닛들의 수입니다.

문제를 해결하기 위한 전략은 다음과 같이 요약할 수 있습니다

  1. 상단과 하단 적의 위치에서 각 건물 행에 대해 독립적으로 공격하는 경우를 확인하여, 해당 행에서의 최소 공격 횟수를 계산합니다.
  2. 상단과 하단을 함께 공격해야 하는 경우를 확인하고, 이에 따른 최소 공격 횟수를 계산합니다.
  3. 연속된 두 행에 걸쳐 상단 또는 하단에서만 공격해야 하는 경우를 확인하고, 이에 따른 최소 공격 횟수를 계산합니다.
  4. 위 세 가지 경우를 조합하여 전체 건물에 대한 최소 공격 횟수를 도출합니다.

이러한 해결 전략을 구현하기 위해 동적 프로그래밍 기법을 사용하여 각 건물의 행에 대해 최소 공격 횟수를 계산하는데 필요한 값을 저장합니다. 동적 프로그래밍 배열은 상단, 하단, 그리고 상단과 하단 모두를 공격하는 경우를 나타냅니다.

문제를 해결하는 데 사용된 주요 아이디어는 가능한 모든 공격 시나리오를 비교하고 그들 중 하나가 최소 공격 횟수가 될 수 있는지 확인하는 것입니다. 이를 위해 적당한 조건들을 반복문 내에 구현하여, 모든 가능한 경우를 확인하며 동적 프로그래밍 배열을 갱신합니다.

결과적으로, 동적 프로그래밍 배열의 마지막 요소를 통해 전체 건물에 대한 최소 공격 횟수를 계산할 수 있습니다. 이 값을 테스트 케이스별로 출력하여 문제를 해결합니다.


예제 입력에 따른 필자의 접근방법

문제

특수 소대들을 이용하여 상단과 하단에 있는 적 유닛을 제거하여 건물을 지키는 데 필요한 최소 공격 횟수를 구하는 문제입니다.
특수 소대는 한 번의 공격으로 한 영역의 상단과 하단에 있는 적 유닛을 모두 처리할 수 있습니다.
그리고 연속된 두 영역의 상단과 하단 모두를 공격하는 경우, 특수 소대는 두 영역에 있는 적 유닛의 합계가 특수 소대의 공격 범위 이내일 경우 처리할 수 있습니다.

해결 전략 및 필자 해석

적 유닛들이 있는 상단과 하단의 각 영역에 대한 합계를 구합니다.
연속된 두 영역에 대해 특수 소대의 공격 범위 내에서 처리할 수 있는 경우를 찾습니다.
인접한 두 영역에 한 번씩 특수 소대를 배치하고, 나머지 영역에도 각각 한 번씩 공격을 가합니다.
이렇게 사용한 공격 횟수를 모두 합쳐서 최소 공격 횟수를 구합니다.
예제 입력 1에 대한 해답에 대한 요약:

주어진 상단과 하단의 적 유닛 정보를 확인하면, 다음과 같이 인접한 영역을 동시에 처리할 수 있는 특수 소대가 필요함을 알 수 있습니다: (2, 3), (5, 6)
이외의 영역 (1, 4, 7, 8)에 각각 한 번씩 공격을 가하면 총 11회의 공격이 필요하게 됩니다.
따라서, 예제 입력 1에 대한 최소 공격 횟수는 11입니다.

profile
컴퓨터공학과에 재학중이며, 백엔드를 지향하고 있습니다. 많이 부족하지만 열심히 노력해서 실력을 갈고 닦겠습니다. 부족하고 틀린 부분이 있을 수도 있지만 이쁘게 봐주시면 감사하겠습니다. 틀린 부분은 댓글 남겨주시면 제가 따로 학습 및 자료를 찾아봐서 제 것으로 만들도록 하겠습니다. 귀중한 시간 방문해주셔서 감사합니다.

0개의 댓글