Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

17. 정수론 및 조합론

정수론과 조합론을 배워 봅시다.

Java / Python

10. 패션왕 신해빈

9375번

경우의 수 연습문제

이번 문제는 조합을 이용하는 문제입니다. 의상 이름과 의상 종류를 입력 받고, 옷의 종류가 중복되지 않게 조합해야 합니다. 같은 종류의 의상은 입을 수 없어, 다른 종류의 의상끼리 구분하여 옷을 조합하는 문제입니다. 공식을 간단하게 정리해보면 (종류별 옷의 수 + 1)을 전부 곱해주고 (해당 종류의 옷을 안 입는 경우의 수를 포함한 것) - 1을 하면 되는 방식입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
 
		int T = Integer.parseInt(br.readLine());	
 
		while (T -- > 0) {
			
			HashMap<String, Integer> hm = new HashMap<>();	// <종류, 개수>
			
			int N = Integer.parseInt(br.readLine());	// 옷의 개수
			
			while (N-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");				
				st.nextToken();	// 옷 이름 고려 X 
				
				String kind = st.nextToken();	// 옷 종류 

				if (hm.containsKey(kind)) {
					hm.put(kind, hm.get(kind) + 1);
				} 
				else {
					hm.put(kind, 1);
				}
			}
 
			int result = 1;
 
			// 안 입는 경우 고려 각 종류별 +1 
			for (int val : hm.values()) {
				result *= (val + 1);
			}
			// 알몸 상태 제외 result - 1
			sb.append(result - 1).append('\n');
 
		}
		System.out.println(sb);
	}
}

• Python

from collections import Counter
import sys
T = int(sys.stdin.readline())
for i in range(T):
    n = int(sys.stdin.readline())
    cloth = []
    for j in range(n):
        a, b = sys.stdin.readline().split()
        cloth.append(b)
    num = 1
    result = Counter(cloth)
    for key in result:
        num *= result[key] + 1
    print(num - 1)