BOJ09375 패션왕 신해빈

https://www.acmicpc.net/problem/9375 (opens new window)

해빈이는 패션에 매우 민감하다고 한다. 한번 입었던 옷들의 조합은 절대 다시 입지 않는다. 또한 의상의 종류 별로 1개를 입거나 안 입을 수 있다.

map에 의상의 종류별 개수를 count한다.

Map<String, Integer> clothes = new HashMap<>();

for (int i = 0; i < n; i++) {
    String type = scanner.next();
    String clothe = scanner.next();
    clothes.put(clothe, clothes.getOrDefault(clothe, 0) + 1);
}

해빈이는 의상의 종류별로 옷을 입을 때와 입지 않을 때의 경우 이기 때문에 모자가 3종류이면 모자에 대한 선택 개수는 3 + 1을 더한 4이다. 또한 각각의 의상의 종류별 개수를 서로 곱하게 되면 해빈이가 입을 수 있는 경우의 수를 구하는 것이다.

int mul = 1;
for (String key : clothes.keySet()) {
    // 아무것도 입지 않는 경우를 고려하여 + 1
    mul *= clothes.get(key) + 1; 
}

마지막으로 주의해야 할 점은 해빈이는 알몸이 아닌 상태는 고려하지 않는다. 적어도 하나의 의상을 선택해야 한다. 즉 아무 것도 입지 않은 경우는 제외해야 한다. 그렇기 때문에 최종적으로 옷을 선택한 경우의 수에서 모두 안입었을 경우를 -1하여 최종 출력한다.

System.out.println(mul - 1);

아래는 최종 제출코드이다.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BOJ9375 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        while (t-- > 0) {

            int n = scanner.nextInt();
            Map<String, Integer> clothes = new HashMap<>();

            for (int i = 0; i < n; i++) {
                String type = scanner.next();
                String clothe = scanner.next();
                clothes.put(clothe, clothes.getOrDefault(clothe, 0) + 1);
            }

            int mul = 1;
            for (String key : clothes.keySet()) {
                mul *= clothes.get(key) + 1;
            }

            System.out.println(mul - 1);
        }
    }
}

#algorithm #BOJ #수학 #자료구조 #해시를 사용한 집합과 맵