이번에는 백준 9375번 패션왕 신해빈 문제를 풀어보았습니다.
이 문제는 옷 이름 자체보다 옷의 종류별 개수가 중요하고,
이를 바탕으로 전체 경우의 수를 계산하는 방식의 문제였습니다.
문제 설명
해빈이는 같은 옷 조합을 다시 입지 않습니다.
주어진 의상 목록을 바탕으로, 알몸이 아닌 상태로 며칠 동안 서로 다른 조합으로 옷을 입을 수 있는지 구해야 합니다.
입력으로는 각 테스트 케이스마다
- 의상의 개수
n - 각 의상의 이름
- 각 의상의 종류
가 주어집니다.
여기서 중요한 점은 같은 종류의 옷은 하나만 입을 수 있다는 점입니다.
즉, 이 문제는 옷 이름을 모두 따지는 것이 아니라
종류별로 몇 개씩 있는지 세는 것이 핵심입니다.
풀이 아이디어
이 문제에서는 같은 종류를 가진 옷의 개수를 세어야 하므로 map<string, int>를 사용했습니다.
예를 들어
- headgear : 2개
- eyewear : 1개
라면, 각 종류마다 선택할 수 있는 경우는 다음과 같습니다.
- headgear → 2개 중 하나를 입거나, 아예 안 입거나 →
2 + 1 - eyewear → 1개를 입거나, 안 입거나 →
1 + 1
즉 전체 경우의 수는
(종류1 개수 + 1) × (종류2 개수 + 1) × ...이 됩니다.
다만 여기에는 모든 종류의 옷을 다 안 입는 경우도 포함되어 있으므로, 마지막에 1을 빼주어야 합니다.
정리하면 결과는 아래 식으로 구할 수 있습니다.
(종류1의 옷 개수 + 1) × (종류2의 옷 개수 + 1) × … - 1처음 구현한 방식 (V1)
처음에는 각 의상 정보를 한 줄 전체 문자열로 입력받고,
split() 함수를 직접 만들어 공백 기준으로 나누는 방식으로 구현했습니다.
코드
#include <bits/stdc++.h>
using namespace std;
map<string, int> clothes_map;
vector<string> split(string str, string delimeter) {
auto begin = 0;
auto end = str.find(delimeter);
vector<string> tokens;
while (end != string::npos) {
tokens.push_back(str.substr(begin, end - begin));
begin = end + 1;
end = str.find(delimeter, begin);
}
tokens.push_back(str.substr(begin));
return tokens;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
int n;
cin >> n;
cin.ignore();
for (int j = 1; j <= n; j++) {
string cloth;
getline(cin, cloth);
vector<string> clothes = split(cloth, " ");
clothes_map[clothes[1]]++;
}
int sum = 1;
for (auto [key, value] : clothes_map) {
sum = sum * (value + 1);
}
sum -= 1;
cout << sum << "\n";
clothes_map.clear();
}
return 0;
}처음 구현에서 같이 정리하게 된 점
이 방식으로 구현하다 보니 자연스럽게 입력 처리도 같이 정리하게 되었습니다.
1. cin.ignore()를 사용한 이유
n을 입력받은 뒤에는 입력 버퍼에 줄바꿈 문자 \n이 남아 있을 수 있습니다.
이 상태에서 바로 getline()을 사용하면,
남아 있던 개행문자를 읽고 빈 문자열이 들어갈 수 있습니다.
그래서 getline() 전에 아래와 같이 cin.ignore()를 사용했습니다.
cin >> n;
cin.ignore();즉, cin.ignore()는 버퍼에 남아 있는 줄바꿈을 지워서
다음 getline()이 정상적으로 한 줄 입력을 받을 수 있게 해주는 역할을 합니다.
2. getline()을 꼭 써야 하나?
이 문제를 다시 보면서 생각해보니,
입력은 항상
의상이름 의상종류형태로 공백 기준 두 개의 문자열로 나뉘어 있었습니다.
그리고 cin >>는 공백을 기준으로 입력을 나누어 읽습니다.
즉, 굳이 한 줄 전체를 getline()으로 받고 직접 나누지 않아도
처음부터 문자열 두 개를 따로 입력받는 방식으로 더 간단하게 처리할 수 있었습니다.
이 부분을 반영해서 두 번째 버전으로 다시 정리했습니다.
간단하게 바꾼 방식 (V2)
두 번째 풀이에서는 getline()과 split()을 없애고,
그냥 cin >> a >> b로 의상 이름과 종류를 바로 입력받도록 바꿨습니다.
코드
#include <bits/stdc++.h>
using namespace std;
map<string, int> clothes_map;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
int n;
cin >> n;
for (int j = 1; j <= n; j++) {
string a, b;
cin >> a >> b;
clothes_map[b]++;
}
int sum = 1;
for (auto [key, value] : clothes_map) {
sum = sum * (value + 1);
}
sum -= 1;
cout << sum << "\n";
clothes_map.clear();
}
return 0;
}풀이 흐름
- 테스트 케이스 개수를 입력받는다.
- 각 테스트 케이스마다 의상 개수
n을 입력받는다. - 의상 이름과 종류를 입력받는다.
map을 사용해 같은 종류의 옷 개수를 센다.- 각 종류마다
(개수 + 1)을 모두 곱한다. - 마지막에 아무 것도 입지 않는 경우를 제외하기 위해
1을 뺀다. - 결과를 출력한 뒤
map을 비운다.
왜 (value + 1)을 곱하고 마지막에 1을 할까
이 문제의 핵심은 이 부분이었습니다.
예를 들어 어떤 종류의 옷이 3개 있다면,
선택할 수 있는 경우는 다음 4가지입니다.
- 첫 번째 옷을 입는다
- 두 번째 옷을 입는다
- 세 번째 옷을 입는다
- 아무 것도 입지 않는다
즉, 옷 개수 + 1개의 선택지가 생깁니다.
이걸 모든 종류에 대해 곱하면 전체 조합 수가 됩니다.
하지만 그 안에는
- 모든 종류에서 아무 것도 선택하지 않는 경우
도 포함되어 있습니다.
문제에서는 알몸이 아닌 상태만 세야 하므로, 마지막에 1을 빼주어야 합니다.
마무리
백준 9375번은 단순한 구현 문제처럼 보이지만,
실제로는 종류별 개수를 세고 경우의 수를 계산하는 방식이 핵심이었습니다.
처음에는 getline()과 split()을 사용해 입력을 처리했지만,
입력 형식을 다시 보면서 cin이 공백 기준으로 입력을 나눈다는 점을 활용해 더 간단하게 바꿀 수 있었습니다.
이번 문제를 통해 정리할 수 있었던 점은 다음과 같습니다.
map으로 같은 종류의 의상 개수를 셀 수 있다- 전체 경우의 수는
(각 종류 개수 + 1)의 곱으로 구할 수 있다 - 마지막에 알몸인 경우를 제외하기 위해
1을 해준다 getline()과cin의 입력 처리 방식 차이도 함께 다시 확인할 수 있다
문제를 풀면서 로직뿐 아니라 입력 처리 방식까지 같이 정리하게 된 문제였습니다.
