[Jungol] 정올 3699 변장

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=3048&sca=2050

Approach

의상 이름은 유일하다고 했으므로 같은 옷이 두 번이상 입력되지 않습니다.

따라서 부류 이름이 몇 번 등장했는지만 세면됩니다. (의상 이름 입력할 필요가 없음)

 

A라는 부류에 속한 의상의 개수가 K개라면 A부류의 의상을 입는 경우의 수는 몇 가지일까?

→ K + 1 (입지 않는 것도 1가지 경우)

따라서 등장한 모든 부류들의 경우의 수를 곱한 결과에서 한 가지(옷을 하나도 입지 않는 경우)를 뺀 결과가 답이 된다.

---

#include <stdio.h>
 
int tc, N, ans;
int cnt, eachCnt[33];
char name[33][22];
 
int strcmp(const char* s, const char *t) {
    while (*s && *s == *t) ++s, ++t;
    return *s - *t;
}
 
void init() {
    ans = 1;
    cnt = 0;
    for (int i = 0; i < 33; ++i) {
        eachCnt[i] = 0;
    }
}
 
void input() {
    scanf("%d", &N);
    int i, j;
    for (i = 0; i < N; ++i) {
        scanf("%*s %s", name[cnt]);
        for(j=0; j<cnt; ++j){
            if (strcmp(name[j], name[cnt]) == 0) break;
        }
        eachCnt[j]++;
        if (j == cnt) cnt++;
    }
}
 
void process() {
    for (int i = 0; i < cnt; ++i) {
        ans *= eachCnt[i] + 1;
    }
}
 
int main() {
    scanf("%d", &tc);
    while (tc--) {
        init();
        input();
        process();
        printf("%d\n", ans - 1);
    }
}

 

STL ver.

#include <iostream>
#include <string>
#include <map>
using namespace std;
 
int main() {
    int tc, N;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d", &N);
        string s, t;
        map<string, int> cntMap;
        int i, ans = 1;
        for (i = 0; i < N; ++i) {
            cin >> s >> t;
            cntMap[t]++;
        }
        for (auto & m : cntMap) ans *= m.second + 1;
        cout << ans - 1 << "\n";
    }
}