[Java] 백준 9375번 - 패션왕 김해빈

문제 링크 : 백준 9375번 - 패션왕 김해빈

 

조합을 구하는 문제다.

 

의상이 종류별로 주어지는 것에 유의하여 종류별 의상의 개수를 구해준 후 조합의 경우의 수를 계산하면 된다.

 

예를 들어

hat adidas

hat bojhat

top thisisneverthat

 

이라는 의상이 들어온다면, 경우의 수는

(hat X) thisisneverthat

adidas (top X)

bojhat (top X)

adidas thisisneverthat

bojhat thisisneverthat

총 5가지다.

 

(hat 종류의 의상 수 + 1) * (top 종류의 의상 수 + 1) - 1 의 공식을 적용해주면 된다.

+1을 더해주는 이유는 해당 종류의 의상을 착용하지 않을 경우를 계산하기 위함이며, 마지막으로 -1을 빼주는 이유는 모든 종류의 의상을 착용하는 경우도 계산되었지만 문제에서 그런 경우는 없으므로 제외해준다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class P9375 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testcase; i++) {
            int N = Integer.parseInt(br.readLine());
            if (N == 0) {
                System.out.println("0");
                continue;
            }

            // Map을 이용해 조합 계산을 위한 의상 종류별 개수를 계산한다.
            HashMap<String, Integer> hashMap = new HashMap<>();
            for (int j = 0; j < N; j++) {
                String[] input = br.readLine().split(" ");
                String type = input[1];
                // 옷을 안 입는 경우까지 2가지 경우를 계산해야 하므로, 개수를 2개로 해준다.

                // 해당 종류의 의상을 처음 map에 넣는 경우
                if (!hashMap.containsKey(type)) hashMap.put(type, 2);
                // 해당 종류의 의상이 이미 map에 있다면, 개수를 1개 더해준다.
                else hashMap.put(type, hashMap.get(type) + 1);
            }
            int mul = 1;
            for (int n : hashMap.values()) {
                mul *= n;
            }
            // 모두 안 입는 경우인 1을 빼준다
            System.out.println(mul - 1);
        }
    }
}