9375 : 패션왕 신해빈 - 경우의 수 여집합 , Map 순회

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

9375번: 패션왕 신해빈

문제요약

서로 다른 패션의 범주, 그 범주안에 속하는 서로 다른 아이템의 종류를 파악,

서로 다른 코디의 경우의 수를 구하는 문제

 

난이도

Silver 3

---

풀이

• 여집합 활용 : 전체 경우의 수 - 해당되지 않는 경우의 수

---

REVIEW

 

서로 다른 주머니, 주머니 안의 서로 다른 공의 종류 이렇게 치환해 생각하고,

1개를 뽑을 때, 2개를 뽑을 때, 3개를 뽑을 때로 뽑는 공을 늘려가며 경우의 수를 더해가려고 했다.

 

그리고 인덱스가 없는 map을 순회할 수 있는지도 의문이어서,

머릿속으로 수도코드가 너무나 복잡해지는 바람에 풀이를 멈추고야 말았다.

 

수학문제는 일단 체력으로라도 풀면되는데, 코딩의 경우 모든 테스트 케이스에 적합한 초월적인 답이 필요하다보니,

요령을 피울 수 없다는 것을 깨달으며..

 

여튼, 조합을 재귀로 구현한다? 아득했다가,

전체 경우의 수에서 해당하지 않는 경우의 수를 빼면 되는구나 아이디어를 얻어 풀었다.

 

너무 복잡해진다 싶으면 역시 단순하게 생각할 필요가 있다.

---

문법정리

• map 순회하는 방법
  • *인덱스가 있는 배열,벡터와는 다른 방식의 순회 방법인듯 한데, 나중에 공부해야겠지만 방문했던 곳은 처리를 해주는 방식으로 모든 요소를 순회하는 듯함
  • auto => iterator가 반환되는듯(?)

map<string, int> _map;

for(auto c: _map)

 

• map.size()
  • map도 전체 크기를 구할 수 있다. 이걸 몰라서 새로운 key값이 나올 때 마다 typecount를 ++해주도록 구현했다..
• 팁 : 경우의 수의 경우 long long으로 넉넉하게 설정해두기

---

CODE

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

int t,n;
string a,b;

int main(){

    cin >> t;

    while(t--){
        map<string,int> _map;
        cin >> n;

        for(int i = 0; i < n; i++){
            cin >> a>> b;
            _map[b]++;
        }

        long long ret = 1;
        for(auto c: _map){  //순회할 수 있구나
            ret *=((long long)c.second + 1);    
        }
        ret--;
        // 전체 경우의 수에서 모든 걸 다 쓰지 않은 경우의 수를 뺴주면 됨.
        cout << ret << "\n";
    }



}