[백준 c++] 9375 패션왕 신해빈

8083 단어 백준CC

문제 설명

https://www.acmicpc.net/problem/9375
겹치지 않는 옷 조합의 개수를 구하는 문제다. 아무것도 고르는 것은 포함하지 않는다.

아이디어

  1. map으로 옷 이름(string)을 입력받아서 해당 second(int)를 ++한다.(잘했어~~~👊)
map<string, int> p;
		
		for (int i = 0; i < n; i++) {
			cin >> x >> s;
			p[s]+=1;
		}
  1. 조합의 수를 어떻게 구할지 혼자 이리저리 계산해보다가 더는 안되겠어서 힌트를 얻었다. 하나도 고르지 않는 경우의 수를 포함해서 계산하고 마지막에 1을 빼주면 된다..대박

  2. map의 second부분인 int만을 추출해서 cnt에 곱하는 계산을 처음에는 배열을 따로 만들어서 second부분을 차례로 저장했었다. 근데 더 컴팩트하게 하는 방법이 있었음.
    +경우의 수를 세는 cnt의 경우 이번엔 int로 맞았지만 long long으로 선언하는게 좋음

//처음코드
		for (auto i = p.begin(); i != p.end(); i++) {
			arr[idx] = i->second+1;
			idx++;
		}
		for (int i = 0; i < idx; i++) {
			cnt *= arr[i];
		}
        
//수정코드
		for (auto c : p) {
			cnt *= (c.second + 1);
		}

👍🙌


전체 코드

#include <iostream>
#include <algorithm>
#include<string>
#include <string.h>
#include <map>

using namespace std;
int n, t;
string x,s;

int main() {
	cin >> t;
	while(t--) {
		int cnt = 1;
		map<string, int>p;
		
        cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> x >> s;
			p[s]+=1;
		}
        
		for (auto c : p) {
			cnt *= (c.second + 1);
		}
		cout << cnt - 1<< "\n";
	}
}

좋은 웹페이지 즐겨찾기