[BOJ] 9375 패션왕 신해빈 JAVA & C++ 문제풀이

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

 

 

#풀이

 

* Map 자료구조와 조합론을 사용해 풀이하였다. 

 

각 테스트 케이스에서 n개의 의상 이름과 의상 종류가 공백으로 구분되어 주어진다.  

이 때 같은 종류의 의상은 하나만 입을 수 있으며, 같은 이름을 가진 의상은 존재하지 않는다.

 

즉 다음과 같이 테스트 케이스가 주어졌다고 가정 시

hat headgear

sunglasses eyewear

turban headgear

의상 종류를 기준으로 케이스를 분류하면 다음과 같다. 

{headgear : hat, turban} , {eyewear : sunglasses}

 

이제 주어진 의상을 가지고 구성할 수 있는 옷의 조합을 구하면 된다.

문제에서 핵심 조건은 다음과 같다.

 

1. 한 번 입었던 옷들의 조합은 다시 입지 않는다.

->  동일한 종류의 의상은 한 번만 선택 가능하다.

2. 알몸이 아닌 상태

-> 의상을 아무것도 고르지 않은 조합은 불가능하다.

 

{headgear : hat, turban} , {eyewear : sunglasses} 옷의 조합을 조합론으로 풀어보면

3C1 * 2C1 - 1 이 된다.

여기서 2C1 {hat, turban} * 1C1 {sunglasses} 이 아닌 이유는 해당 종류의 옷을 고르지 않은 상태를 포함시켜야 하기 때문이다.

따라서  2C1 {hat, truban} * 1C1 {sunglasses} 조합이 아니라

3C1 {hat, truban, Null} * 2C1 {sunglasses, Null} 이 되어야 한다.

마지막에 1을 제외하는 경우는 문제에서 제시한 조건인 "2. 알몸이 아닌 상태" 를 제외하기 위함이다.

 

#Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {

            Map<String, Integer> clothMap = new HashMap<>();
            int res = 1;
            int n = Integer.parseInt(br.readLine());
            for (int j = 0; j < n; j++) {

                StringTokenizer st = new StringTokenizer(br.readLine());
                st.nextToken(); // hat headgear -> 앞의 의상 이름 (hat) 정보는 필요 없으니 버린다.
                String clothType = st.nextToken();
                clothMap.put(clothType, clothMap.getOrDefault(clothType, 0) + 1);

            }

            // 옷장에 존재하는 의상으로 만들 수 있는 모든 조합의 수
            for (String string : clothMap.keySet()) {
                res *= clothMap.get(string) + 1;
            }

            // 아무것도 입지 않은 조합을 제외
            System.out.println(res - 1);
        }
    }
}

 

#C++

#include <unordered_map>
using namespace std;
#include <iostream>

int main() {

    int testCase;
    cin >> testCase;
    for (int i = 0; i < testCase; i++) {
        int n;
        cin >> n;
        unordered_map<string, int> clothMap;
        string clothName, clothType;
        for (int j = 0; j < n; j++) {
            cin >> clothName >> clothType;
            clothMap[clothType]++;
        }

        int res = 1;
        for (const auto& pair : clothMap) {
            res *= pair.second + 1;
        }
        cout << res - 1 << endl;
    }

    return 0;
}