📜 문제
- 해빈이가 옷 하나만 걸쳐도 되니까 나체만 아닌 모든 경우의 수
- 종류별로 한 개만 입을 수 있음
ex) 모자 두 개 안 됨
생각하기
내가 제일 약한 분류인 조합 문제이다.
그런데 걸치는 옷의 조합을 나열하는 게 아닌 단지 경우의 수만 구하는 거라서 수학으로 풀 수 있지 않을까 싶었다. (재귀 짜다가 번뜩 생각남)
하지만, 기껏 짜놓은 재귀가 아깝기도 했고.. 시간도 많이 지나서 그냥 제출하고 25%에서 실패해서 답 봤다.
풀이 방법은 결국 수학이지롱
접근 방식
headgear - hat, turban
eyewear - sunglasses
위와 같이 예제가 주어졌지만, 문제에서는 해빈이가 나체만 아니면 된다고 했다.
즉, 우리는 아래와 같이 아무것도 안 입는 선택지도 분류에 넣어주고 경우의 수를 구해야 한다.
headgear - hat, turban,NONE
eyewear - sunglasses, NONE
그러면, 우리가 구할 수 있는 경우의 수는
headgear 종류에서 1개 * eyewear 종류에서 1개
= ₃C₁X ₂C₁ = 3 X 2 = 6
이때, 두 종류 모두 NONE을 고르는 경우가 포함돼 있으므로 결과값에서 1을 빼주면 답이 된다.
🍳 전체 소스 코드
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc-- >0){
Map<String, Integer> map = new HashMap<>();
int count = Integer.parseInt(br.readLine());
while(count -- >0){
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
String sort = st.nextToken();
map.put(sort, map.getOrDefault(sort,1)+1);
}
long result = 1;
for(String key: map.keySet()){
result*=map.get(key);
}
result-=1;
bw.write(result+"\n");
}
bw.flush();
bw.close();
}
}
✍ 부분 코드 설명
입력
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int tc = Integer.parseInt(br.readLine());
while(tc-- >0){
Map<String, Integer> map = new HashMap<>();
int count = Integer.parseInt(br.readLine());
while(count -- >0){
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
String sort = st.nextToken();
map.put(sort, map.getOrDefault(sort,1)+1);
}
...- Map: key에는 옷의 종류, value에는 해당 종류의 옷 개수를 넣어준다.
경우의 수 구하기
long result = 1;
for(String key: map.keySet()){
result*=map.get(key);
}
result-=1;
bw.write(result+"\n");
}
bw.flush();
bw.close();
}
}- map을 순회 하면서 구한 경우의 수를 result 변수에 삽입한다.
- 나체인 경우의 수가 포함돼 있으니 result에서 1을 제한다.
✨ 결과
조합만 나오면 벌벌 떤다.
이번 문제는 나열하는 게 아니기 때문에 수학적으로 접근하여 푸는 거였지만
나열하라는 문제가 나오는 걸 대비해서 외우든가 알아도야겠다.
📖 참고
