9375번: 패션왕 신해빈

문제

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

• 입력:
  • 첫째 줄: 테스트 케이스의 수 T (최대 100)
  • 각 테스트 케이스의 첫째 줄: 해빈이가 가진 의상의 수 N (0 ≤ N ≤ 30)
  • 다음 N개의 줄: 의상의 이름과 의상의 종류가 공백으로 구분되어 주어짐 (같은 종류의 의상은 하나만 입을 수 있음)
• 출력: 각 테스트 케이스마다 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우의 수

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

풀이

의상의 종류별로 개수를 파악하고, 조합 경우의 수를 구하는 수학 및 해시 맵 문제입니다.

1. 의상 종류별 개수 카운트: HashMap을 생성하여 의상의 종류를 키(Key)로, 해당 종류의 의상 개수를 값(Value)으로 저장합니다. 입력받은 의상의 이름은 중복되지 않으므로 개수만 파악하면 됩니다.
2. 조합의 수 계산: 각 의상 종류별로 '입지 않는 경우'를 포함해야 하므로, 종류별 의상 개수에 1을 더한 값들을 모두 곱해줍니다.
3. 알몸인 경우 제외: 모든 의상을 입지 않은 상태(알몸)는 문제 조건에 따라 불가능하므로, 전체 조합의 수에서 1을 빼줍니다.

코드

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

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));

       int t = Integer.parseInt(br.readLine());
       while (t-- > 0) {
          int n = Integer.parseInt(br.readLine());
          Map<String, Integer> map = new HashMap<>();
          for (int i = 0; i < n; i++) {
             StringTokenizer st = new StringTokenizer(br.readLine());
             st.nextToken(); // 의상 이름은 조합 수 계산에 필요 없으므로 무시
             String s = st.nextToken(); // 의상 종류
             map.put(s, map.getOrDefault(s, 0) + 1);
          }

          int ans = 1;
          for (int i : map.values()) {
             ans *= i + 1; // 해당 종류의 옷을 입지 않는 경우를 포함하여 곱함
          }

          bw.write((ans - 1) + "\n"); // 모두 입지 않는 경우 1가지를 뺌
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

수학 (Math), 자료구조 (Data Structure), 해시를 사용한 집합과 맵 (Hash Map), 조합론 (Combinatorics)