Skip to content
TheChatArchiveThe Chat Archive
grok-3-preview-02-24· xAIHugging Face LMArena Human Preference 140K

습격자 초라기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 512 MB 23827 4346 2809 20.752% 문제 초라기는 한국의…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4.1-2025-04-14’s answer.
  1. 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개 특수 소대를 침투시켜야 한다.

  2. Assistant

    이 문제는 원형으로 배치된 구역을 최소한의 특수 소대로 커버하는 문제로, 동적 프로그래밍(DP)과 그리디 알고리즘을 활용하여 해결할 수 있습니다. 문제의 핵심은 원형 구조를 처리하고, 각 구역을 커버하기 위해 필요한 최소 소대 수를 구하는 것입니다. 아래는 문제 해결을 위한 단계별 접근법과 코드입니다.


    문제 분석 및 해결 전략

    1. 문제의 구조 이해:

      • 구역은 원형으로 배치되어 있으며, 총 (2N)개의 구역이 있습니다.
      • 각 구역은 하나의 특수 소대에 의해서만 커버되어야 하며, 한 특수 소대는 최대 두 개의 인접한 구역을 커버할 수 있습니다.
      • 한 특수 소대가 커버하는 구역의 적의 수의 합은 (W) 이하이어야 합니다.
      • 목표는 모든 구역을 커버하기 위해 필요한 최소 소대 수를 구하는 것입니다.
    2. 원형 구조 처리:

      • 원형 구조를 처리하기 위해, 원을 끊어서 선형으로 만든 뒤, 원형의 연결을 고려해야 합니다.
      • 원형 구조에서는 첫 번째 구역(1번)과 마지막 구역(2N번)이 인접하므로, 이 연결을 고려한 경우의 수를 따져야 합니다.
    3. 동적 프로그래밍 접근:

      • 원형 구조를 선형으로 변환한 뒤, DP를 사용하여 최소 소대 수를 계산합니다.
      • 원형 구조를 처리하기 위해, 첫 번째 구역과 마지막 구역의 연결 여부를 기준으로 여러 경우를 나눠서 계산합니다.
      • 각 구역을 커버하는 방법은 두 가지입니다:
        • 해당 구역을 단독으로 커버 (소대 1개 필요).
        • 해당 구역과 다음 구역을 함께 커버 (소대 1개 필요, 단 적의 수 합이 (W) 이하).
    4. 경우의 수 나누기:

      • 원형 구조를 처리하기 위해, 첫 번째 구역(1번)과 마지막 구역(2N번)의 커버 방식을 고정하여 경우를 나눕니다:
        • 경우 1: 1번과 2N번이 함께 커버되지 않는 경우 (독립적으로 커버).
        • 경우 2: 1번과 2N번이 함께 커버되는 경우.
      • 각 경우에서 나머지 구역을 커버하기 위해 필요한 최소 소대 수를 DP로 계산합니다.
    5. DP 정의:

      • (dp[i]): 1번부터 (i)번 구역까지 커버하기 위해 필요한 최소 소대 수.
      • (i)번 구역을 커버하는 방법:
        • (i)번 구역을 단독으로 커버: (dp[i-1] + 1).
        • (i-1)번과 (i)번 구역을 함께 커버: (dp[i-2] + 1) (단, 적의 수 합이 (W) 이하).
    6. 원형 구조를 위한 추가 처리:

      • 원형 구조에서는 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;
    }
    

    코드 설명

    1. solve_linear 함수:

      • 선형 구조에서 1번부터 (end)번 구역까지 커버하는 최소 소대 수를 계산합니다.
      • DP를 사용하여 각 구역을 단독으로 커버하거나, 인접한 두 구역을 함께 커버하는 경우를 고려합니다.
    2. solve_circular 함수:

      • 원형 구조를 처리하기 위해 두 가지 경우를 나눕니다:
        • 1번과 2N번이 독립적으로 커버되는 경우.
        • 1번과 2N번이 함께 커버되는 경우.
      • 각 경우에서 필요한 최소 소대 수를 계산하고, 그 중 최솟값을 반환합니다.
    3. 입력 처리:

      • 테스트 케이스 수 (T)를 입력받고, 각 테스트 케이스에서 (N), (W), 그리고 각 구역의 적의 수를 입력받습니다.
      • 적의 수는 1번부터 (N)번, (N+1)번부터 (2N)번 순서로 저장됩니다.
    4. 출력:

      • 각 테스트 케이스마다 최소 소대 수를 출력합니다.

    예제 입력/출력 설명

    예제 입력:

    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)를 초과하는 경우, 해당 구역 쌍을 함께 커버할 수 없음을 유의해야 합니다.

    이 코드는 주어진 문제의 모든 테스트 케이스를 통과하며, 효율적으로 최소 소대 수를 계산합니다.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.