[swea-D2] 16811. 당근 포장하기
문제
이싸피는 싸피 식당에 당근을 공급하고 있다. 이싸피의 당근은 맛도 있지만, 영양분이 풍부해 당근을 먹은 사람들이 알고리즘 문제를 더 잘 풀게 된다고 한다. 하지만 이싸피도 싸피 식당의 복잡한 포장 조건 때문에 늘 고생하고 있다.
싸피식당의 요구 조건은 다음과 같다.
N개의 당근을 주문하면 대, 중, 소 상자로 구분해 포장해야 한다. 같은 크기의 당근은 같은 상자에 들어있어야 한다. 비어 있는 상자가 있으면 안 된다.
한 상자에 N/2개(N이 홀수면 소수점 버림)를 초과하는 당근이 있어서도 안 된다.
앞의 조건을 만족하면서도, 각 상자에 든 당근의 개수 차이가 최소가 되도록 포장해야 한다. 그리고 이때의 개수 차이를 서류에 표시 한다.
새로운 주문이 들어와 이싸피는 N개의 당근을 밭에서 뽑아왔다. 대, 중, 소 상자를 각각 저울에 올려 포장해보는 대신, 뽑은 당근의 크기를 입력하면 모든 조건을 확인하는 프로그램을 만들어 이싸피가 쉽게 당근을 포장할 수 있게 도와보자.
예시1)
뽑아온 당근이 3개이고, 크기가 1 2 3이라면 다음과 같이 포장할 수 있다.
소 [ 1 ], 중 [ 2 ], 대 [ 3 ], 상자에 든 당근의 개수 차이는 0
예시2)
당근이 5개이고 크기가 1 1 1 2 3 이라면, 조건 (1)~(3)을 만족하는 포장은 다음과 같다.
1
소[ 1 1 1 ], 중 [ 2 ], 대 [ 3 ], 당근의 개수 차이는 2
하지만 이 경우 5/2개(2개)를 초과하는 상자가 있으므로 조건(4)를 만족하지 못한다.
예시3)
당근이 8개 이고, 크기가 1 2 3 4 5 6 7 8인 경우이다. 우선 다음과 같이 포장할 수도 있다.
1
소[ 1 2 3 4 ], 중[ 5 ], 대[ 6 7 8 ], 당근의 개수 차이는 3
하지만 다음과 같이 포장해야 조건(5)를 만족한다.
1
소[ 1 2 3 ], 중[ 4 5 6 ], 대[ 7 8 ], 당근의 개수 차이는 1
또는 다음과 같은 경우도 조건(5)를 만족한다.
1
소[ 1 2 ], 중[ 3 4 5 ], 대[ 6 7 8 ], 당근의 개수 차이는 1
[입력]
첫 줄에 총 수확 횟수 T가 주어진다.
각 수확에 대해, 첫 줄에 당근의 개수N, 다음 줄에 수확한 N개의 당근 크기 Ci가 빈칸으로 구분되어 주어진다. ( 3<=N<=1000, 1<=Ci<=30 )
[출력]
#과 1번부터인 수확번호에 이어, 포장 할 수 없는 경우 -1, 포장할 수 있으면 상자에 들어있는 당근의 개수 차이가 최소일 때의 차이값을 출력하라.
입력
1
2
3
4
5
6
7
8
9
4
14
1 1 1 2 2 2 2 2 3 4 5 6 7 8 9
3
1 2 3
5
1 1 1 2 3
8
1 2 3 4 5 6 7 8
출력
1
2
3
4
#1 4
#2 0
#3 -1
#4 1
🙋♂️ 들어가며
먼저 조건을 정리해보자
- 3개의 상자 (소, 중, 대)
- 같은 크기는 같은 상자에
- 빈상자 X -> 최소 1개 보장
- 한상자 : N/2 초과 -> 불가능
구간을 써볼까?
구간의 갯수 = (끝 - 시작 + 1)
1
2
3
소 : (0 ~ i)
중 : (i+1 ~ j)
대 : (j+1 ~ N-1)
그러면 같은 크기는 같은 상자에 있어야 하니
조건을 잘 짜야겠다
testcase 1번 보자
1
1 1 1 2 2 2 2 2 3 4 5 6 7 8 9
N = 14
i = 2
j = 7
1
2
3
소 : (i+1)
중 : j-(i+1)+1
대 : N-1 -(j+1)+1
상자의 숫자는 2가지 경우로 나뉜다
- 같은 쌍이 있거나
- 전부 다르거나
같은 쌍이 있을 경우에는
small, medium, large 에 겹치면 안되니 아래 조건이 필요하다
1
2
if (arr[i] == arr[i+1]) continue;
if (arr[j] == arr[j+1]) continue;
이제 코드를 보자
✅ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc < T+1; tc++) {
int N = Integer.parseInt(br.readLine());
String[] arr = br.readLine().split(" ");
int[] C = new int[N];
for (int i = 0; i < N; i++) {
C[i] = Integer.parseInt(arr[i]);
}
// 1. 정렬
Arrays.sort(C);
// 2. 경계선 설정
// 한 상자에 최소 1개는 보장
// 구간의 갯수 : (끝점 - 시작점 + 1)
// (0 ~ i), (i+1 ~ j), (j+1 ~ N-1)
int min_diff = Integer.MAX_VALUE;
for (int i = 0; i < N-2; i++) {
for (int j = i+1; j < N-1; j++) {
// 2-1. 같은 숫자는 같은 상자에
if (C[i] == C[i+1]) continue;
if (C[j] == C[j+1]) continue;
int small_box = (i-0) + 1;
int medium_box = j -(i+1) + 1;
int large_box = (N-1) -(j+1) + 1;
// 2-1. N/2면 skip
if (small_box > N/2 || medium_box > N/2 || large_box > N/2) continue;
// 2-2. 빈 박스면 skip
if (small_box == 0 || medium_box == 0 || large_box == 0) continue;
// 2-3. 위 기준에 해당되지 않는다면
int max = Math.max(small_box, Math.max(medium_box, large_box));
int min = Math.min(small_box, Math.min(medium_box, large_box));
// 2-4. 최소값 갱신
int temp_diff = Math.abs(max-min);
min_diff = Math.min(temp_diff, min_diff);
}
}
// 3. 출력
if (min_diff == Integer.MAX_VALUE) {
System.out.println("#" + tc + " " + -1);
}
else {
System.out.println("#" + tc + " " + min_diff);
}
}
}
}
