λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
✨ Algorithm

[λ°±μ€€/C++] 9375번 : νŒ¨μ…˜μ™• μ‹ ν˜œλΉˆ

by nitronium102 2021. 9. 12.

문제

ν•΄λΉˆμ΄λŠ” νŒ¨μ…˜μ— 맀우 λ―Όκ°ν•΄μ„œ ν•œλ²ˆ μž…μ—ˆλ˜ μ˜·λ“€μ˜ 쑰합을 μ ˆλŒ€ λ‹€μ‹œ μž…μ§€ μ•ŠλŠ”λ‹€. 예λ₯Ό λ“€μ–΄ 였늘 ν•΄λΉˆμ΄κ°€ μ•ˆκ²½, μ½”νŠΈ, μƒμ˜, μ‹ λ°œμ„ μž…μ—ˆλ‹€λ©΄, λ‹€μŒλ‚ μ€ 바지λ₯Ό μΆ”κ°€λ‘œ μž…κ±°λ‚˜ μ•ˆκ²½λŒ€μ‹  렌즈λ₯Ό μ°©μš©ν•˜κ±°λ‚˜ ν•΄μ•Όν•œλ‹€. ν•΄λΉˆμ΄κ°€ 가진 μ˜μƒλ“€μ΄ μ£Όμ–΄μ‘Œμ„λ•Œ κ³Όμ—° ν•΄λΉˆμ΄λŠ” μ•ŒλͺΈμ΄ μ•„λ‹Œ μƒνƒœλ‘œ λ©°μΉ λ™μ•ˆ 밖에 λŒμ•„λ‹€λ‹ 수 μžˆμ„κΉŒ?

μž…λ ₯

첫째 쀄에 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€κ°€ 주어진닀. ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€λŠ” μ΅œλŒ€ 100이닀.

  • 각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ˜ 첫째 μ€„μ—λŠ” ν•΄λΉˆμ΄κ°€ 가진 μ˜μƒμ˜ 수 n(0 ≤ n ≤ 30)이 μ£Όμ–΄μ§„λ‹€.
  • λ‹€μŒ nκ°œμ—λŠ” ν•΄λΉˆμ΄κ°€ 가진 μ˜μƒμ˜ 이름과 μ˜μƒμ˜ μ’…λ₯˜κ°€ 곡백으둜 κ΅¬λΆ„λ˜μ–΄ 주어진닀. 같은 μ’…λ₯˜μ˜ μ˜μƒμ€ ν•˜λ‚˜λ§Œ μž…μ„ 수 μžˆλ‹€.

λͺ¨λ“  λ¬Έμžμ—΄μ€ 1이상 20μ΄ν•˜μ˜ μ•ŒνŒŒλ²³ μ†Œλ¬Έμžλ‘œ μ΄λ£¨μ–΄μ ΈμžˆμœΌλ©° 같은 이름을 가진 μ˜μƒμ€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€.

좜λ ₯

각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ— λŒ€ν•΄ ν•΄λΉˆμ΄κ°€ μ•ŒλͺΈμ΄ μ•„λ‹Œ μƒνƒœλ‘œ μ˜μƒμ„ μž…μ„ 수 μžˆλŠ” 경우λ₯Ό 좜λ ₯ν•˜μ‹œμ˜€.

풀이

이 λ¬Έμ œμ—μ„œ μ˜μƒμ˜ 이름은 μ€‘μš”ν•˜μ§€ μ•Šλ‹€! μ˜μƒ μ’…λ₯˜λ³„ 개수만 μ•Œλ©΄ λœλ‹€

 

(μ˜μƒ μ’…λ₯˜λ³„ 옷 수 + μ„ νƒν•˜μ§€ μ•ŠλŠ” 경우 1가지)λ₯Ό λ”ν•΄μ„œ 닡에 κ³±ν•΄μ€€ ν›„, λ§ˆμ§€λ§‰μ— 아무것도 μ•ˆ μž…λŠ” 경우λ₯Ό μ œμ™Έ

// ex) head : a, b,

 

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

int main(){
    int t, n, ans=1;
    string name, type;
    cin >> t;

    while(t--){
        cin >> n;
        map<string, int> cloth;
        while (n--){ // map에 μ €μž₯
            cin >> name >> type;
            cloth[type]++;
        }
        for (auto & iter : cloth){ // 옷 μž…λŠ” κ°€μ§“μˆ˜
            ans *= iter.second + 1; // μ’…λ₯˜λ³„ 옷 수 + μ„ νƒν•˜μ§€ μ•ŠλŠ” 경우 1가지
            // ex) head : a, b, ∅
            // ex) eye : c, ∅
        }
        ans--; // {∅ , ∅} 인 경우 μ œμ™Έ
        cout << ans << "\n";
        ans = 1;
    }
}

λŒ“κΈ€