[백준] no9375: 패션왕 신해빈

문제

: 주어진 옷을 타입별로 겹치지 않게 1개 이상 입는 경우의 수 구하기

T: 테스트 케이스 수

M : 각 테스트당 주어지는 옷 가지 수

 

문제 링크 : https://www.acmicpc.net/problem/9375

---

원리

자료구조(Map)를 이용한 조합 수 구하기

A개 中 1,  B개 中 1, C개 中 1, D개 中 1을 골라 입는 경우 = A*B*C*D

A개 中 1,  B개 中 1, C개 中 1, D개 中 1을 골라 입는 경우 = (A+1)*(B+1)*(C+1)*(D+1) [0개 가능 할 때]

---

풀이방법

1. 각 타입별 옷을 카운트 한다

2. 카운트 한 값에 안입는 경우 +1 해서 모두 곱한다

3. 아무고토 안입는 경우 1만큼 빼준다

---

나의 코드

public class no9375 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 테스트 케이스별 반복
        for(int i=0; i<T ; i++) {
            int M = Integer.parseInt(br.readLine());
            Map<String, Integer> map = new HashMap<>(); // 각 타입별 옷을 넣을 맵

            // 옷 담기
            for(int j=0; j<M; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                st.nextToken(); // 이름은 중요치 않음
                String type = st.nextToken(); // 중요한건 타입별 몇개씩 있느냐
                map.put(type, map.getOrDefault(type, 0) + 1); // 해당 타입에 든게 있으면 +1, 없으면 0 +1 시작
            }

            int style = 1;
            for(int value : map.values()) style *= value + 1; // 특정 type을 입지 않는 경우가 있으므로, +1 하여 곱해줌

            System.out.println(style - 1);  // 하나도 안입는 경우를 제거하기 위해 -1
        }
    }
}

---

레퍼런스 코드

참고 링크 : https://girawhale.tistory.com/19