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

#문제

9375번: 패션왕 신해빈

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

9375번: 패션왕 신해빈

 

---

#접근방법

수학문제이다. 문자열을 구분하기 위해 자료구조 map을 사용해주었다.

반응형

---

#풀이

#include <stdio.h>
#include <iostream>
#include <map>
using namespace std;

int main(){
    int t,n;
    map<string,int>::iterator iter;
    string a,b;
    int ans;

    scanf("%d",&t);

    while(t--){
        map<string,int> m;

        scanf("%d",&n);

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

            m[b]++;
        }

        ans = 1;

        for(iter=m.begin();iter!=m.end();iter++)
            ans *= (iter->second+1);

        printf("%d\n",ans-1);
    }

    return 0;
}

 

먼저 테스트케이스가 주어지고 케이스마다 n개의 옷조합이 주어진다.

 

hat headgear와 같이 의상의 이름, 의상의 종류로 주어진다. 이 때, 의상의 이름은 모두 다르다.

 

예를들어 같은 의상이 3개가 있으면 3개를 입는 경우 + 안입는 경우로 총 4가지의 경우의 수가있다.

 

따라서 의상의 종류별로 개수를 map에 저장하여 반복문을 통해 각 의상의 개수 + 1을 다 곱해준 다음 알몸인 경우 1가지를 빼면 경우의 수를 구할 수 있다.

 

map<string,int> m으로 자료형을 만들어 주었다. 그리고 n개의 옷을 입력받을 때 마다 m[b]++을 해주었는데 의상의 이름이 다 다르기 때문에 중복은 생각안해도 된다.

 

n개의 옷을 다 입력받았으면 map 자료구조를 반복문으로 돌면서 ans *= (iter->second+1)을 해준다.

 

ans-1을 출력하면 정답이다.

---

#성능

---

#정리

의상을 입을 수 있는 경우의 수를 구하는 방법을 아는 것,

 

map 자료구조를 통해 문자열을 구분할 수 있으면 쉽게 풀 수 있는 문제였다.