[BOJ] 9375: 패션왕 신해빈 (JAVA)

문제

https://www.acmicpc.net/problem/9375

 

여담

모든 조합을 계산하는 방법에 대해 계속 고민하다가 풀이를 참고했다. 복잡하게만 생각했었는데 풀이를 보고 이렇게 간단하게 계산할 수 있구나..? 하고 놀랐다.. 이럴 때마다 머리의 한계를 느껴..

 

생각한 방법이 아닌 것 같으면 시야를 넓혀보는 습관을 가지자 제발!

 

풀이

문제에 따르면, 같은 종류끼리는 입을 수 없다. 따라서 우선 종류별로 옷의 개수를 센다.

• headgear - 2개 (hat, turban)
• eyewear - 1개 (sunglasses)

 

그 후, 입을 수 있는 모든 방법의 수를 구해야 한다. 따라서 한 종류만 입는 경우, 두 종류만 입는 경우, ..., N 종류를 입는 경우와 같이 모든 경우를 계산해야 한다. 

• 한 종류만 입는 경우
  • answer = 2 + 1 = 3, 총 3가지
• 두 종류만 입는 경우
  • answer = 2 * 1 = 2, 총 2가지
• 따라서 총 5가지

 

모든 경우를 쉽게 계산하기 위해 옷을 입지 않는 것을 뜻하는 null이 있다고 생각하면 편하다.

 

hat + null, turban + null은 한 종류만, hat + sunglasses는 두 종류를 입는 것을 뜻한다. 따라서 종류별로 구분한 옷의 개수에 1을 더해준다. 그 후, 옷의 개수끼리 곱하고 아무것도 입지 않는 상태인 null + null 조합을 없애기 위해 1을 빼주면 된다.

• headgear
  • hat, turban, null (3개)
• eyewear
  • sunglasses, null (2개)
• 따라서 총 5가지 (`3 × 2 - 1 = 5`)

 

코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            HashMap<String, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                String name = st.nextToken();
                String kind = st.nextToken();
                if (hashMap.containsKey(kind)) {
                    hashMap.put(kind, hashMap.get(kind) + 1);
                } else {
                    hashMap.put(kind, 1);
                }
            }

            List<Integer> list = hashMap.values().stream().collect(Collectors.toList());
            int ans = 1;
            for (int l : list) {
                ans *= l + 1;
            }
            sb.append(ans - 1).append("\n");
        }
        System.out.println(sb.toString());
    }
}

---

참고

https://st-lab.tistory.com/164