BOJ 9375 - 패션왕 신해빈

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

문제

해빈이가 가진 의상들의 이름과 종류가 주어지면, 가능한 모든 경우의 수는 몇 개인지 묻는 문제입니다.

문제에서 같은 이름을 가진 의상은 존재하지 않으므로 이름은 중요하지 않고 해당 종류만 구분하면 됩니다.

가지고 있는 모자가 2개라면 모자만으로 가능한 경우는 3가지입니다. 첫 번째를 쓰거나, 두 번째를 쓰거나, 아무것도 쓰지 않거나 이렇게 총 3가지입니다.

어떤 종류를 $n$개 가지고 있다면 선택 가능한 수는 $n+1$개이고, 나올 수 있는 모든 가짓수는 각 종류마다 가능한 경우를 모두 곱한 값입니다.

위 그림의 경우에는 $3 \times 4 \times 2~=~24$ 이지만, 문제에서 알몸이 아닌 상태 즉 모두 선택하지 않는 경우는 제외했으므로 1을 뺀 $23$이 정답입니다.

완전히 동일한 문제가 프로그래머스 연습 문제 고득점 Kit에도 있습니다.

코드

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long lld;
	int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
	int n;
	scanf("%d ", &n);
	map<string, int> types;
	while (n--) {
	char name[21], type[21];
	scanf("%s %s ", name, type);
	types[type] += 1;
	}
	map<string, int>::iterator it = types.begin();
	lld ans = 1;
	for (; it != types.end(); ++it) {
	ans *= (it->second + 1);
	}
	printf("%lld\n", ans - 1);
	}
	return 0;
	}

view raw boj-9375.cpp hosted with ❤ by GitHub

비슷한 문제

• 프로그래머스 - 코딩테스트연습 > 해시 > 위장