[swea-D3] 4223. 삼성이의 트라우마 극복
# [swea-D3] 4223. 삼성이의 트라우마 극복
문제
S회사는 공채 시즌후 탈락자들에게는 N명의 면접관들이 해당 탈락자에게 각 면접관이 부여한 면접 점수를 공개한다.
면접점수는 각 면접관들마다 주고싶은 점수 P를 줄 수 있다.
삼성이는 지난 공채에서 S회사에 지원했지만 입사면접에서 떨어졌다.
떨어진것도 슬픈데 자신의 탈락점수를 확인하곤 면접 트라우마에 걸려버렸다.
그러나 이대로 포기할 삼성이가 아니다. 삼성이는 면접 트라우마를 극복하기 위해 곰곰히 고민하기 시작했다.
평소 문자를 좋아하던 삼성이는 자신을 떨어뜨린 면접관들의 이름에서 각각의 단어를 뽑아 그 단어를 조합해서 SAMSUNG이라는 문자열을 만든다면 트라우마 극복에 도움이 될것같다.
면접관들의 이름을 조합해서 SAMSUNG을 만들때 각 면접관 점수의 합의 최소값을 구하면 면접대비를 더 잘하게 되고, 다음 공채에서는 합격도 가능할 것 같다.
우리 모두 삼성이가 트라우마를 극복하고 다음 공채에서는 꼭 합격할 수 있도록 도와주자!
1
2
3
4
5
6
7
8
9
10
11
12
예시)
1 //테스트케이스 T
3 //면접관수 N
3 //1번 면접관이름의 길이 L
S A M //1번 면접관 이름
50 //1번 면접관의 점수 P
4 //2번 면접관이름의 길이 L
S A M S //2번 면접관 이름
20 //2번 면접관의 점수 P
4 //3번 면접관이름의 길이 L
S U N G //3번 면접관의이름
25 //3번면접관의 점수 P
위와 같은 상황일때 SAMSUNG 이라는 문자열을 만드는 방법은 2가지가 있다.
1번 면접관의 이름 SAM과 3번 면접관의 이름 SUNG 에서 각각의 단어를 뽑아 조합하면 SAMSUNG이라는 글자가 만들어진다 (면접점수의 합 50 + 25)
2번 면접관의 이름 SAMS와 3번 면접관의 이름 SUNG에서 각각의 단어를 뽑아 조합하면 SAMSUNG을 만들고 S라는문자가 남지만 상관없다. 남는건 버리면 된다. (면접점수의합 20 + 25)
이때 점수의 합의 최소값은 2번 3번 면접관의 이름을 조합했을때 두 면접관의 점수의 합인 45가 최소값이다.
[제약사항]
면접관의 수(N)는 1 이상 10 이하의 정수이다. (1<=N<=10)
이름의 길이는 1 이상 10 이하의 정수이다. (1<=L<=10)
면접관의 이름은 영어이며 항상 대문자로 표시된다.
면접관의 점수는 개별점수로 각각 다를수도, 같을수도 있으며 0이상 1000이하의 정수이다. (0<=P<=1000)
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고,
그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 면접관의 수 N이 주어진다.
그 다음 N번동안 각각 3줄에 걸쳐 각각의 줄에 면접관 이름의 길이 L, 면접관의 이름(공백을 두고 대문자로 주어진다), 면접관의 점수 P가 주어진다.
[출력]
테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 “#t”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t 는 1부터 시작하는 테스트 케이스의 번호이다.)
면접관들의 이름의 단어를 조합해서 SAMSUNG을 만들 수 있을 때 각 면접관들의 점수의 합의 최소값을 출력한다.
만약 SAMSUNG이라는 단어를 만들 수 없다면 -1을 출력한다.
입력
1
2
3
4
5
6
7
8
9
10
11
1
3
3
S A M
50
4
S A M S
20
4
S U N G
25
출력
1
#1 45
🙋♂️ 들어가며
이 문제는 백트랙킹마다 검사를 통해 최소합을 갱신할 수 있다.
✅ 코드
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;
public class Solution {
static int N;
static int min_sum;
static String[] name;
static List<Integer> lst_num;
static List<String> lst_s;
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++) {
// 0. min_sum 초기화
min_sum = Integer.MAX_VALUE;
// 1. 각 lst 생성 (int, String)
lst_num = new ArrayList<>();
lst_s = new ArrayList<>();
N = Integer.parseInt(br.readLine());
for (int n = 0; n < N; n++) {
int L = Integer.parseInt(br.readLine());
name = br.readLine().split(" ");
int P = Integer.parseInt(br.readLine());
String s = "";
for (int i = 0; i < name.length; i++) {
s += name[i];
}
lst_num.add(P);
lst_s.add(s);
}
// 1-2. back_tracking
boolean[] visited = new boolean[N];
back_tracking(0, visited);
// 1-3. 조건
if (min_sum == Integer.MAX_VALUE) {
min_sum = -1;
}
System.out.println("#" + tc + " " + min_sum);
}
}
// 2-1. back_tracking 함수
static void back_tracking(int idx, boolean[] visited) {
// 2-2. 검사
calculate(visited);
// 2-3. 가지치기
if (idx >= N) return;
// 2-4-a 선택
visited[idx] = true;
back_tracking(idx+1, visited);
// 2-4-b 미선택
visited[idx] = false;
back_tracking(idx+1, visited);
}
// 3. 검사 함수
static void calculate(boolean[] visited) {
int[] dict = new int[26];
int temp_sum = 0;
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
String temp_s = lst_s.get(i);
int temp_num = lst_num.get(i);
// 3-1. dict -> 숫자 추가
for (int j = 0; j < temp_s.length(); j++) {
int cur_s = temp_s.charAt(j) - 'A';
dict[cur_s]++;
}
temp_sum += temp_num;
}
}
// 3-2. SAMSUNG 만들 수 있다면?
if (dict['S'-'A'] >= 2 && dict['A'-'A'] >= 1 && dict['M'-'A'] >= 1 && dict['U' - 'A'] >= 1 && dict['N' - 'A'] >= 1 && dict['G' - 'A'] >= 1) {
min_sum = Math.min(temp_sum, min_sum);
}
}
}
