[백준][9375] 패션왕 신해빈

이 포스트는 백준 사이트의 패션왕 신해빈 문제 풀이입니다.

문제

제약 확인

문제의 입력 조선에서 “같은 종류의 의상은 하나만 입을 수 있다.” 라고 하였으므로
옷의 각 종류에서 선택되는 것은 1개 입니다.

풀이

이 문제는 해시맵을 사용하여 간단하게 풀 수 있는 문제입니다.
예시 문제를 통해 수식을 만들고 코드를 작성해 보겠습니다.

3개의 옷이 입력되고 종류는 headgear와 eyewear가 있으며 각각 2개, 1개가 존재합니다.
먼저, headgear는 hat, turban 이 선택되거나 아예 선택되지 않는 경우가 있습니다.
그리고 eyewear 에서는 sunglasses 가 선택되거나 선택되지 않는 경우가 있습니다.
따라서 위의 headgear 경우의 수 3과 eyewear 경우의 수 2 를 곱하고
문제의 조건처럼 알몸인 경우(모든 옷 종류를 선택하지 않음)만 빼면 정답을 알 수 있습니다.

\[(모자 종류 개수 + 1) \times (안경 종류 개수 + 1) \times ... \times (바지 종류 개수 + 1) - 1\]

#include <iostream>
#include <unordered_map>
#include <algorithm>

#define INPUT_SETTINGS cin.tie(0)->sync_with_stdio(false)

using namespace std;

unordered_map<string, int> clothing;

int get_clothing_combination_count() {
    int answer = 1;
    for(auto curr : clothing) {
        answer *= (curr.second + 1);
    }
    return answer - 1;
}

void input() {
    int T, N;
    string name, type;
    cin >> T;
    while(T--) {
        cin >> N;

        clothing.clear();
        while(N--) {
            cin >> name >> type;
            clothing[type] += 1;
        }

        printf("%d\n", get_clothing_combination_count());
    }
}

int main() {
    input();
    return 0;
}

출처

[BOJ] 패션왕 신해빈