https://www.acmicpc.net/problem/9375
해당 문제 같은경우는 hash_map 자체에 대한 이해도를 묻기보단 문제를 해석하는 센스와 수학적인 경우의수를 어떻게 쉽게 구할 수 있는지가 쟁점인 문제다. 입력으로 옷의 이름과 옷의 종류를 입력받는데 옷의 이름은 겹치지 않으므로 경우의 수를 구할 때 옷의 종류 만 생각하면 된다. 예를 들어서 옷의 종류가
양말, 모자, 상의 라고 가정하고 각각 다른 양말2개, 모자3개, 상의2개가 있다고 가정해보자
- 양말 안에서 선택할 수 있는 경우의수는 양말1 or 양말2 or 양말 선택 x 총3개
- 모자 안에서 선택할 수 있는 경우의수는 모자1 or 모자2 or 모자3 or 모자 선택 x 총4개
- 상의 안에서 선택할 수 있는 경우의수는 상의1 or 상의2o or 상의 선택 x 총 3개 이다.
따라서 신해빈님이 입을 수 있는 경우의수는 쉽게 3x4x3이다 36개이다 BUT 아무것도 안 입는 경우의수는 없다고 했으므로 양말 선택X, 모자 선택 X, 상의 선택X 인 경우 1개를 빼줘서 35개 가 된다. 이 원리를 빠르게 생각하면 쉬운 문제이고 이 원리를 빨리 생각하지 못하면 산으로 가는 문제라고 생각한다. 풀이는 아래와 같다 내용만 이해하면 굉장히 쉽다.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
int t, n;
int main()
{
cin >> t;
while(t--)
{
int ans=1;
unordered_map<string, int> um;
cin >> n;
string name, type;
for(int i=0; i < n ; i ++)
{
cin >> name >> type ;
um[type]++;
}
for(auto & c : um)
{
ans=ans*(c.second+1);
}
cout << ans -1 << '\n';
}
}
바킹독님 풀이
// Authored by : heheHwang
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/20eb099e71a94245b5ef25f23214130a
#include
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
unordered_map<string, int=""> clothings;
int N, ans = 1;
cin >> N;
string a, b;
while (N--) {
cin >> a >> b;
clothings[b]++;
}
for (auto v : clothings) ans *= v.second + 1;
cout << ans - 1 << '\n'; // 알몸인 경우를 제외합니다.
}
}</string,>
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 1202번: 보석 도둑(C++) (0) | 2024.01.31 |
---|---|
백준 7662번: 이중 우선순위 큐 (C++) (0) | 2024.01.31 |
백준 17219번: 비밀번호 찾기 [C++] (0) | 2024.01.31 |
백준 13414번: 수강신청 [C++] (0) | 2024.01.31 |
백준 1620번: 나는야 포켓몬 마스터 이다솜 [C++] (0) | 2024.01.31 |