습격자 초라기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 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
이 문제는 원형 2줄(도넛 형태)의 구역을 최소의 특수소대로 커버하는 최적 커버링 문제입니다.
각 소대는 한 구역 또는 인접한 두 구역을 커버할 수 있고, 커버하는 구역의 적의 합이 W 이하여야 합니다.핵심 아이디어
- 2줄의 원형 배열이므로, 각 줄은 1
N, 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)입니다.
궁금한 점 있으면 추가로 질문해주세요!
- 2줄의 원형 배열이므로, 각 줄은 1
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.