[백준, 자바, 9375번] 패션왕 신해빈

풀이

• 해당 문제는 물론 재귀로 해서 문제를 해결할 수는 있지만
• 수학적 규칙이 보여서 고민해보다가
• 예전 수학 규칙이 생각남
• 우선 예를 들어 3개의 의상 종류가 있을 경우
• 모자 3개, 상의 2개, 바지 2개라고 할 경우
• 각각 1개씩 착용한 것, 2개씩, 3개씩 착용한 경우에 대한
• 모든 경우의 수를 더해야 하기에
• 착용하지 않은 수를 각 의상 별로 하나씩 추가
• 따라서 모자 4개, 상의 3개, 바지 3개로 생각 후
• 모든 경우의 수를 구해야 하므로 4*3*3을 하면 36개
• 단, 여기서 모든 것을 착용하지 않은 하나의 경우를 뺀다면 35개 식으로 구하기로 함
• 그래서 다음과 같이 코드를 작성
• 그리고 같은 이름의 의상은 없다고 했는데 체크 못해서... Set로 받은것...

 

import java.io.*;
import java.util.*;

public class _9375 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static Map<String, Set<String>> dic;
    public static void main(String[] args) throws IOException {

        int T = Integer.parseInt(br.readLine());
        while (T>0) {
            dic = new HashMap<>();
            int N = Integer.parseInt(br.readLine());
            addMap(N);
            bw.write(counting()+"\n");
            T--;
        }
        bw.flush();
    }

    private static void addMap(int N) throws IOException {
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            String v = st.nextToken();
            String k = st.nextToken();
            if (!dic.containsKey(k)) dic.put(k,new HashSet<>(Arrays.asList(v)));
            else dic.get(k).add(v);
        }
    }

    private static int counting() {
        int result = 1;
        for (Set<String> li: dic.values()) result*=li.size()+1;
        return result-1;
    }
}

// 1 2 3
// 4 5
// 6 7

// 1 2 3 4 5 6 7 = 7
// 14 15 16 17, 24 25 26 27, 34 35 36 37,  46 47, 56 57 = 16
// 146 147 156 157, = 12

// 35 = > 7+12+(6+6+4)16