[9375] 패션왕 신해빈

[Java]

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

9375번: 패션왕 신해빈

 

[문제]

1. 해빈이는 옷을 n개 가지고 있으며, 옷은 이름과 종류가 있습니다.(0≤n≤30)
2. 같은 종류의 의상은 하나만 입을 수 있으며, 같은 이름을 가진 의상은 존재하지 않습니다.
3. 입력 첫 째줄에는 Test case 수가 들어오며
4. Test case별로 첫 줄에는 가지고 있는 의상의 개수가 입력됩니다.
5. 이후 의상의 개수 행만큼 의상 이름과 의상 종류가 공백으로 구분되어 입력됩니다.
6. Test case별로 1개 이상의 옷을 입을 수 있는 모든 경우의 수를 출력하시오.

이름의 이름은 중요하지 않으며, 의상의 종류별로 몇 개의 옷이 들어왔는지 파악해 조합의 경우의 수를 구하는 문제입니다.

 

[코드]

import java.io.*;
import java.util.StringTokenizer;
import java.util.HashMap;

public class Main {
		
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;		
		
		int t = Integer.parseInt(br.readLine());
		
		for(int i = 0; i<t; i++) {
			HashMap<String,Integer> dic = new HashMap<String,Integer>();
			String key="";
			int cnt = 0;
			
			int n = Integer.parseInt(br.readLine());
			for(int j = 0; j<n; j++) {
				st = new StringTokenizer(br.readLine());
				st.nextToken(); //같은 이름을 가진 의상은 존재하지 않으니, 의상 이름은 사용하지 않겠습니다.
				key = st.nextToken();
				if(dic.containsKey(key))
					cnt = dic.get(key);
				else
					cnt=0;
				dic.put(key, cnt+1);
			}
			
			int sum = 1;
			for(int j : dic.values()) {
				sum*=(j+1);//안입은 경우를 포함하여 +1
			}
			bw.write(String.valueOf(sum-1)+'\n');//전부 안입었을 때는 없으니 -1 해준다.
		}
		br.close();
		bw.close();
	}
}

 

[풀이]

1. HashMap을 이용하여 의상 종류별로 개수를 count 해줍니다.
2. 해당 종류의 옷을 안입는 선택지도 하나의 경우로 포함해 종류 별로 sum에 선택지 만큼 곱합니다.
3. 마지막으로 모든 종류의 옷을 안입을 수는 없기에 경우의 수에서 -1을 해줍니다.

해당 문제의 풀이와 코드는 간단하나 안입는 경우를 경우에 수에 포함하는 것을 생각하지 못해 상당히 오랜 시간이 소요된문제 입니다.