[코딩테스트] 경우의 수 구하기

1. 종류별 포함

int main()
{
    // 입력 값
    vector<pair<string, string>> v = { 
    	{"yellow_hat", "headgear"}, 
   	{"blue_sunglasses", "eyewear"}, 
   	{"green_turban", "headgear"} 
   };
    
    // 경우의 수 카운트
    int resultCount = 1;
    
    // 각 종류별 의상 수
    unordered_map<string, int> myMap;
    
    // 종류별 의상 수 카운트
    for(auto& a : v)
    {
        ++myMap[a.second];
    }
    
    // 종류별 최소 1개 포함 공식
    for(auto& a : myMap)
    {
        resultCount *= a.second;
    }
    
    cout << resultCount; // 2
    
    return 0;
}

위의 경우 headgear에서는 "yellow_hat", "green_turban"이 가능하고, eyewear에서는 "blue_sunglasses"만 가능하므로 경우의 수는 2 * 1 = 2이다.

 

2. 종류별 미포함 가능

int main()
{
    // 입력 값
    vector<pair<string, string>> v = { 
    	{"yellow_hat", "headgear"}, 
   	{"blue_sunglasses", "eyewear"}, 
   	{"green_turban", "headgear"} 
   };
    
    // 경우의 수 카운트
    int resultCount = 1;
    
    // 각 종류별 의상 수
    unordered_map<string, int> myMap;
    
    // 종류별 의상 수 카운트
    for(auto& a : v)
    {
        ++myMap[a.second];
    }
    
    // 종류별 미포함 가능 포함 공식
    for(auto& a : myMap)
    {
        resultCount *= (a.second+1);
    }
    
    cout << resultCount; // 6
    
    return 0;
}

위의 경우 headgear에서는 "yellow_hat", "green_turban", "x"이 가능하고, eyewear에서는 "blue_sunglasses", "x"가 가능하므로 경우의 수는 (2+1) * (1+1) = 6이다.