[백준] 9375번 : 패션왕 신해빈 | C++

0. 문제

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

 

---

1. 문제풀이 핵심

 

만들 수 있는 조합의 개수 계산

• 각 의상 종류별로 가능한 조합을 구합니다. 의상을 입지 않는 경우와 해당 의상을 입는 경우를 모두 고려하면 (의상 종류의 개수 + 1)이 됩니다.
• 모든 의상 종류별 조합을 곱한 후, 모든 의상을 입지 않는 경우(즉, 알몸인 경우)를 제외하기 위해 결과에서 1을 뺍니다.

 

** 모든 조합을 구하는 것이 아닌, 조합의 개수만 구하는 문제이기 때문에 기존 조합을 구하는데 사용되는 알고리즘(next_permutation, 재귀 등)이 사용되지 않습니다. 

 

---

2. 문제풀이에 사용된 개념

map을 활용한 데이터 저장

• map을 사용하여 각 의상 종류와 그 개수를 저장합니다.
• 이미 존재하는 의상 종류인지 확인하고, 해당하는 경우 value를 증가시킵니다.
• 존재하지 않는 경우 새로운 의상 종류를 추가합니다.

 

map.insert({type, 1})

요소 추가하기 

map.insert({type, 1});

 

 

 

map.find(type) != map.end()

요소 찾기 & 요소 값 수정하기

auto it = map.find(type);
if (it != map.end()) { // 이미 의상 종류에 따른 아이템이 존재하는 경우
    it->second++; // 의상 개수 증가
}else{
    // 의상 종류와 개수 추가
    map.insert({type,1});
}

 

 

 

 

 

---

 

3. 문제풀이 코드

#include<bits/stdc++.h>

using namespace std;

int t; //테케 개수

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> t;
    while(t--){
        int n; //보유한 의상 개수
        cin >> n;

        if (n==0){
            cout << "0\n";
            continue; // 옷이 없는 경우 예외처리 
        }

        map<string,int> c; //의상 종류, 종류별 의상 개수

        while(n--){ //종류별로 옷 입력받기
            string cname, type;
            cin >> cname >> type;

            auto it = c.find(type);
            if(it != c.end()){
                it -> second++; 
            }else{ 
                c.insert({type,1});
            }
        }

        int ans =1;
        //종류별로 가능한 조합 구하기 
        for(auto it =c.begin(); it != c.end(); it++){
            int combiPerC = it -> second +1;
            ans *= combiPerC;
        }
        cout << ans-1<<'\n';
    }
}

 

3-1. 코드 로직 설명

결국 종류별 가능한 조합의 개수를 다 곱하고 , 그 중에 모두 안입은 경우인 1을 빼주면 된다 

근데 여기에서 옷이 없는 케이스를 처리할 때, cout <<"0";이라고 해서 한번 틀렸다. cout<<"0\n"라고 했어야했는데..

이런 실수는 조심하자 

 

• 의상을 종류별로 처리:
  • 각 테스트 케이스마다 보유한 의상 개수를 입력받습니다.
  • 의상의 종류를 map에 저장하여 의상 종류별 개수를 관리합니다.
• 조합 계산:
  • 각 의상 종류별로 "안 입는 경우"를 고려해 (의상 개수 + 1)을 더한후, 모든 조합의 곱을 구합니다.
  • 모두 안 입는 경우(알몸인 경우)를 제외하기 위해 최종 결과에서 1을 뺍니다.
• 예외 처리:
  • 보유한 의상이 없는 경우(0개)에는 결과로 0을 출력합니다.

 

 

주의사항

• 보유한 의상이 없는 경우에 대한 예외처리 출력 시 cout << "0\n"; 로 줄 바꿈을 포함해야 합니다. 이 부분에서 cout<<"0"을 하여 틀리게 되었다는...

 

 

 

---

 

4. 문제풀이에 사용된 함수

 

map.find(key)

• key를 이용하여 map에서 해당 키를 가진 요소를 찾습니다.
• 찾으면 해당 요소의 이터레이터를 반환하고, 찾지 못하면 map.end()를 반환합니다.

map.insert({key, value})

• key-value 쌍을 map에 추가합니다.
• 중복된 키가 없을 때만 추가됩니다.

 

이터레이터를 통한 접근

• it->second를 통해 해당 키의 값을 불러오거나 연산을 추가할 수 있습니다.

---

 

5. 요약 정리

 

• 핵심 아이디어: 의상 종류별로 입는 경우와 입지 않는 경우를 모두 고려하여 가능한 조합의 수를 구하고, 모든 경우의 조합을 곱합니다. 그 후 알몸인 경우를 제외하기 위해 1을 뺍니다.
• map 활용: string을 기준으로 데이터를 저장하는 구조가 필요하므로 map을 사용합니다. 이를 통해 의상의 종류별로 개수를 관리하고, [ 종류별 개수 +1 ] 한 경우의 수를 다 곱해주어 결과값을 계산합니다. 

+) 주의사항

- 예외 처리에서의 출력 형식에 주의하여야 합니다.(나자신..)