[BOJ] 9375 패션왕 신해빈

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

9375번: 패션왕 신해빈

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

map or hash

 

---------------------------------------------------풀이----------------------------------------------------

 

key가 옷 종류 이름, value가 옷의 개수인 map을 사용한다.

옷의 종류마다 개수를 세서 map에 저장하였다.

어떤 옷 종류에 대해 k개가 존재한다고 하면, 옷을 선택하지 않거나 i번째(i<=k) 옷을 선택하는 경우가 있으므로 총 k+1개의 케이스가 존재한다.

모든 옷 종류에 대해 k+1가지씩의 선택지가 있으므로

모든 경우의 수를 세면 (각 종류의 개수+1)의 곱이 나오는 것을 알 수 있고,

여기서 모든 옷을 선택하지 않는 케이스를 빼야 하므로

(각 종류의 개수+1)의 곱 - 1 이 정답이다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <map>

using namespace std;

int main(void){
    FASTIO;
    int T;
    cin >> T;
    while(T--){
        // 총 의상의 수
        int n;
        cin >> n;
        map<string, int> m;
        string name, type;
        for(int i = 0; i < n; i++){
            cin >> name >> type;
            map<string, int>::iterator it = m.find(type);
            // 이미 옷 타입이 존재하면 개수+1
            if(it != m.end()){
                it->second++;
            }
            // 새로운 타입이면 개수 = 1
            else{
                m[type] = 1;
            }
        }
        // (type의 개수+1)들의 곱 - 1이 정답.
        int ans = 1;
        for(auto it = m.begin(); it != m.end(); it++){
            ans *= (it->second+1);
        }
        cout << ans-1 << "\n";
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이전에 프로그래머스에서 푼 문제와 유사하다.