Skip to content
TheChatArchiveThe Chat Archive
gpt-4.1-2025-04-14· OpenAIHugging 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 grok-3-preview-02-24’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

    이 문제는 원형 2줄(도넛 형태)의 구역을 최소의 특수소대로 커버하는 최적 커버링 문제입니다.
    각 소대는 한 구역 또는 인접한 두 구역을 커버할 수 있고, 커버하는 구역의 적의 합이 W 이하여야 합니다.

    핵심 아이디어

    • 2줄의 원형 배열이므로, 각 줄은 1N, N+12N 구역입니다.
    • 각 구역은 **상하좌우(원형이므로 양 끝도 연결)**로 인접합니다.
    • **DP(동적 계획법)**로 해결할 수 있습니다.

    1. 문제 해석

    • 각 구역은 한 소대만 커버할 수 있습니다.
    • 한 소대는 한 구역 또는 인접한 두 구역(상하, 좌우, 원형 연결 포함)을 커버할 수 있습니다.
    • 모든 구역을 커버해야 하며, 최소 소대 수를 구해야 합니다.

    2. 접근 방법

    1) 인접 구역 커버링

    • 가로(좌우) 커버: (i, i+1) (원형이므로 N과 1도 연결)
    • 세로(상하) 커버: (i, i+N)

    2) DP 정의

    • dp[i][a][b]: i번째 열까지 커버했을 때,
      • a: 윗줄(i)이 커버됐는지(0/1)
      • b: 아랫줄(i)이 커버됐는지(0/1)
      • 최소 소대 수

    3) 원형 처리

    • 양 끝(1, N)도 연결되어 있으므로,
      시작할 때 (1, N) 가로 커버를 했는지 여부에 따라 경우를 나눠야 합니다.

    3. 코드 구현

    아래는 파이썬 코드입니다.

    import sys
    input = sys.stdin.readline
    
    def solve(N, W, up, down):
        INF = 1 << 30
        res = INF
    
        # 4가지 경우: (윗줄 1번, 아랫줄 1번) (가로 커버) 여부
        for up_pair in [False, True]:
            for down_pair in [False, True]:
                # 불가능한 경우 skip
                if up_pair and up[0] + up[-1] > W:
                    continue
                if down_pair and down[0] + down[-1] > W:
                    continue
    
                dp = [[INF]*3 for _ in range(N)]
                # 0: 둘 다 안 남음, 1: 윗줄만 남음, 2: 아랫줄만 남음
    
                # 첫 칸 처리
                if up_pair and down_pair:
                    dp[0][0] = 2
                elif up_pair:
                    dp[0][2] = 1
                    dp[0][0] = 1
                elif down_pair:
                    dp[0][1] = 1
                    dp[0][0] = 1
                else:
                    dp[0][0] = 0
    
                # 첫 칸에서 세로 커버 가능하면
                if up[0] + down[0] <= W:
                    dp[0][0] = min(dp[0][0], 1)
    
                for i in range(1, N):
                    # 윗줄 가로 커버
                    if up[i-1] + up[i] <= W:
                        dp[i][0] = min(dp[i][0], dp[i-1][2] + 1)
                    # 아랫줄 가로 커버
                    if down[i-1] + down[i] <= W:
                        dp[i][0] = min(dp[i][0], dp[i-1][1] + 1)
                    # 세로 커버
                    if up[i] + down[i] <= W:
                        dp[i][0] = min(dp[i][0], dp[i-1][0] + 1)
                    # 각각 커버
                    dp[i][1] = min(dp[i][1], dp[i-1][0] + 1)
                    dp[i][2] = min(dp[i][2], dp[i-1][0] + 1)
                    # 아무것도 안함
                    dp[i][0] = min(dp[i][0], dp[i-1][0] + 2)
                    # 윗줄만 남음
                    dp[i][1] = min(dp[i][1], dp[i-1][2] + 1)
                    # 아랫줄만 남음
                    dp[i][2] = min(dp[i][2], dp[i-1][1] + 1)
    
                # 마지막 칸 처리
                if up_pair and down_pair:
                    res = min(res, dp[N-1][0])
                elif up_pair:
                    res = min(res, dp[N-1][2])
                elif down_pair:
                    res = min(res, dp[N-1][1])
                else:
                    res = min(res, dp[N-1][0])
    
        return res
    
    T = int(input())
    for _ in range(T):
        N, W = map(int, input().split())
        up = list(map(int, input().split()))
        down = list(map(int, input().split()))
        print(solve(N, W, up, down))
    

    4. 설명

    • 4가지 경우(윗줄 1번, 아랫줄 1번 가로 커버 여부)에 대해 모두 시도합니다.
    • 각 경우마다 DP로 최소 소대 수를 계산합니다.
    • 최소값을 출력합니다.

    참고

    • 이 문제는 백준 1006번 습격자 초라기와 동일합니다.
    • 시간복잡도는 O(N)입니다.

    궁금한 점 있으면 추가로 질문해주세요!

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