습격자 초라기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 23827 4346 2809 20.752% 문제 초라기는 한국의…
- User
습격자 초라기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 23827 4346 2809 20.752% 문제 초라기는 한국의 비밀국방기지(원타곤)를 습격하라는 임무를 받은 특급요원이다. 원타곤의 건물은 도넛 형태이며, 초라기는 효율적인 타격 포인트를 정하기 위해 구역을 아래와 같이 두 개의 원 모양으로 나누었다. (그림의 숫자는 각 구역의 번호이다.)
초라기는 각각 W명으로 구성된 특수소대를 다수 출동시켜 모든 구역에 침투시킬 예정이며, 각 구역 별로 적이 몇 명씩 배치되어 있는지는 초라기가 모두 알고 있다. 특수소대를 아래 조건에 따라 침투 시킬 수 있다.
한 특수소대는 침투한 구역 외에, 인접한 한 구역 더 침투할 수 있다. (같은 경계를 공유하고 있으면 인접 하다고 한다. 위 그림에서 1구역은 2, 8, 9 구역과 서로 인접한 상태다.) 즉, 한 특수소대는 한 개 혹은 두 개의 구역을 커버할 수 있다. 특수소대끼리는 아군인지 적인지 구분을 못 하기 때문에, 각 구역은 하나의 소대로만 커버해야 한다. 한 특수소대가 커버하는 구역의 적들의 합은 특수소대원 수 W 보다 작거나 같아야 한다. 이때 초라기는 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 알고 싶어 한다.
입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 구성되어있다.
첫째 줄에는 (구역의 개수)/2 값 N과 특수 소대원의 수 W가 주어진다. (1 ≤ N ≤ 10000, 1 ≤ W ≤ 10000).
둘째 줄에는 1~N번째 구역에 배치된 적의 수가 주어지고, 셋째 줄에는 N+1 ~ 2N번째 구역에 배치된 적의 수가 공백으로 구분되어 주어진다. (1 ≤ 각 구역에 배치된 최대 적의 수 ≤ 10000) 단, 한 구역에서 특수 소대원의 수보다 많은 적이 배치된 구역은 존재하지 않는다. (따라서, 각 구역에 배치된 최대 적의 수 ≤ W)
출력 각 테스트케이스에 대해서 한 줄에 하나씩 원타곤의 모든 구역을 커버하기 위해 침투 시켜야 할 특수 소대의 최소 개수를 출력하시오.
예제 입력 1 1 8 100 70 60 55 43 57 60 44 50 58 40 47 90 45 52 80 40 예제 출력 1 11 힌트 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소대를 침투시켜야 한다.
- Assistant
이 문제는 원형으로 배치된 구역을 최소한의 특수 소대로 커버하는 문제로, 동적 프로그래밍(DP)과 그리디 알고리즘을 활용하여 해결할 수 있습니다. 문제의 핵심은 원형 구조를 처리하고, 각 구역을 커버하기 위해 필요한 최소 소대 수를 구하는 것입니다. 아래는 문제 해결을 위한 단계별 접근법과 코드입니다.
문제 분석 및 해결 전략
-
문제의 구조 이해:
- 구역은 원형으로 배치되어 있으며, 총 (2N)개의 구역이 있습니다.
- 각 구역은 하나의 특수 소대에 의해서만 커버되어야 하며, 한 특수 소대는 최대 두 개의 인접한 구역을 커버할 수 있습니다.
- 한 특수 소대가 커버하는 구역의 적의 수의 합은 (W) 이하이어야 합니다.
- 목표는 모든 구역을 커버하기 위해 필요한 최소 소대 수를 구하는 것입니다.
-
원형 구조 처리:
- 원형 구조를 처리하기 위해, 원을 끊어서 선형으로 만든 뒤, 원형의 연결을 고려해야 합니다.
- 원형 구조에서는 첫 번째 구역(1번)과 마지막 구역(2N번)이 인접하므로, 이 연결을 고려한 경우의 수를 따져야 합니다.
-
동적 프로그래밍 접근:
- 원형 구조를 선형으로 변환한 뒤, DP를 사용하여 최소 소대 수를 계산합니다.
- 원형 구조를 처리하기 위해, 첫 번째 구역과 마지막 구역의 연결 여부를 기준으로 여러 경우를 나눠서 계산합니다.
- 각 구역을 커버하는 방법은 두 가지입니다:
- 해당 구역을 단독으로 커버 (소대 1개 필요).
- 해당 구역과 다음 구역을 함께 커버 (소대 1개 필요, 단 적의 수 합이 (W) 이하).
-
경우의 수 나누기:
- 원형 구조를 처리하기 위해, 첫 번째 구역(1번)과 마지막 구역(2N번)의 커버 방식을 고정하여 경우를 나눕니다:
- 경우 1: 1번과 2N번이 함께 커버되지 않는 경우 (독립적으로 커버).
- 경우 2: 1번과 2N번이 함께 커버되는 경우.
- 각 경우에서 나머지 구역을 커버하기 위해 필요한 최소 소대 수를 DP로 계산합니다.
- 원형 구조를 처리하기 위해, 첫 번째 구역(1번)과 마지막 구역(2N번)의 커버 방식을 고정하여 경우를 나눕니다:
-
DP 정의:
- (dp[i]): 1번부터 (i)번 구역까지 커버하기 위해 필요한 최소 소대 수.
- (i)번 구역을 커버하는 방법:
- (i)번 구역을 단독으로 커버: (dp[i-1] + 1).
- (i-1)번과 (i)번 구역을 함께 커버: (dp[i-2] + 1) (단, 적의 수 합이 (W) 이하).
-
원형 구조를 위한 추가 처리:
- 원형 구조에서는 1번과 2N번이 인접하므로, 이 경우를 별도로 처리해야 합니다.
- 또한, 원형 구조에서는 2N-1번과 2N번, 1번과 2번 등 인접한 구역 쌍을 고려해야 합니다.
구현
아래는 위 전략을 바탕으로 작성한 C++ 코드입니다.
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; const int INF = 1e9; // 1번부터 end까지 구역을 커버하는 최소 소대 수를 계산하는 함수 int solve_linear(vector<int>& enemies, int W, int start, int end) { int n = end - start + 1; if (n <= 0) return 0; vector<int> dp(n + 1, INF); dp[0] = 0; // 초기 상태: 구역을 커버하지 않음 for (int i = 1; i <= n; i++) { // i번 구역을 단독으로 커버 dp[i] = dp[i - 1] + 1; // i-1번과 i번 구역을 함께 커버 (가능한 경우) if (i >= 2 && enemies[start + i - 2] + enemies[start + i - 1] <= W) { dp[i] = min(dp[i], dp[i - 2] + 1); } } return dp[n]; } // 원형 구조를 처리하며 최소 소대 수를 계산하는 함수 int solve_circular(vector<int>& enemies, int W, int N) { int total = 2 * N; int min_squads = INF; // 경우 1: 1번과 2N번이 함께 커버되지 않는 경우 // 1번부터 2N번까지 선형으로 처리 min_squads = solve_linear(enemies, W, 0, total - 1); // 경우 2: 1번과 2N번이 함께 커버되는 경우 if (enemies[0] + enemies[total - 1] <= W) { // 1번과 2N번을 하나의 소대로 커버하고, 나머지 구역(2번부터 2N-1번)을 처리 int squads = 1 + solve_linear(enemies, W, 1, total - 2); min_squads = min(min_squads, squads); } return min_squads; } int main() { int T; cin >> T; while (T--) { int N, W; cin >> N >> W; vector<int> enemies(2 * N); // 첫 번째 줄: 1번부터 N번 구역 for (int i = 0; i < N; i++) { cin >> enemies[i]; } // 두 번째 줄: N+1번부터 2N번 구역 for (int i = 0; i < N; i++) { cin >> enemies[N + i]; } // 원형 구조를 처리하며 최소 소대 수 계산 int result = solve_circular(enemies, W, N); cout << result << "\n"; } return 0; }
코드 설명
-
solve_linear함수:- 선형 구조에서 1번부터 (end)번 구역까지 커버하는 최소 소대 수를 계산합니다.
- DP를 사용하여 각 구역을 단독으로 커버하거나, 인접한 두 구역을 함께 커버하는 경우를 고려합니다.
-
solve_circular함수:- 원형 구조를 처리하기 위해 두 가지 경우를 나눕니다:
- 1번과 2N번이 독립적으로 커버되는 경우.
- 1번과 2N번이 함께 커버되는 경우.
- 각 경우에서 필요한 최소 소대 수를 계산하고, 그 중 최솟값을 반환합니다.
- 원형 구조를 처리하기 위해 두 가지 경우를 나눕니다:
-
입력 처리:
- 테스트 케이스 수 (T)를 입력받고, 각 테스트 케이스에서 (N), (W), 그리고 각 구역의 적의 수를 입력받습니다.
- 적의 수는 1번부터 (N)번, (N+1)번부터 (2N)번 순서로 저장됩니다.
-
출력:
- 각 테스트 케이스마다 최소 소대 수를 출력합니다.
예제 입력/출력 설명
예제 입력:
1 8 100 70 60 55 43 57 60 44 50 58 40 47 90 45 52 80 40예제 출력:
11- 위 예제에서는 총 16개의 구역이 있으며, 각 구역의 적의 수와 (W=100)을 바탕으로 최소 소대 수를 계산합니다.
- 최적의 배치는 일부 구역 쌍을 함께 커버하고, 나머지 구역을 단독으로 커버하여 총 11개의 소대가 필요합니다.
시간 복잡도
- 각 테스트 케이스에서 (2N)개의 구역을 처리하므로, DP 계산의 시간 복잡도는 (O(N))입니다.
- 원형 구조를 처리하기 위해 경우를 나누므로, 전체 시간 복잡도는 (O(T \cdot N))입니다.
- 공간 복잡도는 (O(N))입니다.
주의 사항
- 원형 구조를 처리할 때, 첫 번째와 마지막 구역의 연결을 반드시 고려해야 합니다.
- 각 구역은 정확히 하나의 소대에 의해서만 커버되어야 하므로, 중복 커버를 방지해야 합니다.
- 적의 수 합이 (W)를 초과하는 경우, 해당 구역 쌍을 함께 커버할 수 없음을 유의해야 합니다.
이 코드는 주어진 문제의 모든 테스트 케이스를 통과하며, 효율적으로 최소 소대 수를 계산합니다.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.