P9375. 패션왕 신해빈

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

9375번: 패션왕 신해빈

설명

처음 시도

조합으로 각 경우의 수를 구하고 만들어진 조합끼리 값을 곱하여 result를 구했다.

but! 시간초과 발생⚡️ 

➡️ 생각해보면 각 조합을 모두 구할 필요는 없다! 우리는 경우의 수만 구하면 되기 때문이다. 

 

다음 시도

각각의 종류가 가질 수 있는 경우의 수에 NULL(안 입을 경우)을 추가한다.

headgear: hat, turban, NULL

eyewear: sunglasses, NULL

headgear에서 3C1을 구하면 -> 3

eyewear에서 2C1을 구하면 -> 2

3C1 x 2C1을 곱하여 종류별로 조합하는 공식을 구한다.

+) 알몸이 아닌 상태로 며칠까지 가능한지 구하는 것이므로 1을 빼준다. 

따라서 3C1 x 2C1 - 1 = 3 * 2 - 1 = 5가 답이 된다.

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int t, n, result;
    static Map<String, Integer> clothes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());
            clothes = new HashMap<>();
            for (int j = 0; j < n; j++) {
                String[] str = br.readLine().split(" ");
                int cnt = clothes.getOrDefault(str[1], 1);
                clothes.put(str[1], cnt + 1);
            }

            result = 1;

            for (int val : clothes.values()) {
                result *= val;
            }
            sb.append(result - 1).append("\n");
        }
        System.out.println(sb);
    }

}

 

Reference

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