Baekjoon 9375번 패션왕 신해빈

문제

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

걸린 시간

01 : 38 : 35 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n; // 의상 수
        cin >> n;
        string dress, kind;
        map<string, int> m;
        for(int i = 0; i < n; i++){
            cin >> dress >> kind;
            // 따로 key, value 를 쌍으로 추가하지
            // 않아도 value 값은 항상 0으로
            // 초기화 되어있는 것 같다.
            m[kind] += 1;
        }
        int ans = 1;
        for(auto it = m.begin(); it != m.end(); it++)
            ans *= it->second+1;
        cout << ans-1 << "\n";
    }
    return 0;
}

의상을 map 을 이용해서 종류별로 모두 정리해두고 답을 어떻게 구해야할 지 고민했다.

next_permutation stl 을 이용하여 모든 부분집합을 구해 가능한 모든 경우의 수를 구해야 하는가 싶었다.

그렇게 삽질을 하다 1시간이 넘어갔고 풀이가 너무 복잡한게 방향을 잘못 잡은것 같아 다른 사람의 답을 보니 정말 간단했다.

각 종류별로 의상의 개수에 1씩을 더하여 모두 곱해준 후 1을 뺀 값이 정답이다.

1씩을 더해주는건 입지 않았을 경우를 말하고, 계산된 결과에서 1을 빼는건 아무것도 입지 않는 경우이다.

아래 첨부한 블로그에 설명이 잘 되어있다.

참고

• BOJ 9375 - 패션왕 신해빈 - Joonas' Note - 티스토리