[백준] 정수론및조합론 - 9375번 패션왕 신해빈 java 자바

문제

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

9375번: 패션왕 신해빈

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

 

풀이

옷이 겹치면 안되기 때문에 옷의 종류를 조합하여 나올 수 있는 개수를 구하면 된다. 이때 알몸인 상태 = 모든 종류에서 null을 고른 상태면 안 되기 때문에 마지막에 -1을 해준다.

HashMap을 이용해서 종류별로 옷의 개수를 저장한다. 해당 종류의 옷을 안 입는 경우를 고려해야하므로 종류별로 +1을 해주어야 한다.

 

코드

package 정수론및조합론;
import java.util.*;

public class No9375_패션왕신해빈 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for(int t=0;t<T;t++) {
			int n=sc.nextInt();
			HashMap<String, Integer> map=new HashMap<>();
			
			for(int i=0;i<n;i++	) {
				String name = sc.next();
				String kind = sc.next();
				
				if(map.containsKey(kind))
					map.put(kind, map.get(kind)+1);
				else
					map.put(kind, 1);
				
			}
			
			int answer=1;
			//+1하는 이유 : null까지 포함(해당 종류 옷 안입는 경우)
			for(int val:map.values())
				answer*=(val+1);
			
			System.out.println(answer-1); //모두 null 선택하는 경우 제외 
		}
	}

}