문제
풀이
- N이 최대 100,000이 들어오기 때문에 모든 경우의 수를 탐색하면 시간초과가 발생한다.
- 비둘기 집 원리에 관련되어 있는 문제이며, MBTI의 종류가 16개이기 때문에 N이 32보다 큰 경우 아무리 거리를 멀리하려고 MBTI 입력을 받아도 반드시 3개가 중복되는 것이 존재하여 32보다 큰 경우 정답은 반드시 0이다. 이 사실을 이용하여 N이 32이하인 경우에만 모든 경우의 수를 탐색하고 그렇지 않으면 0을 출력한다.
참고 : 시간 초과 오류가 떠서 계속 고생했는데 시간 초과 오류는 시간복잡도 때문에 나오기도 하지만 입력을 받지 않고 기다려서 나는 경우도 있다. 이 문제의 경우 32보다 큰지 아닌지를 N개의 MBTI를 모두 입력 받은 다음에 판단하여야 입력 때문에 시간초과가 나오는 경우를 피할 수 있다.
시간 초과가 난 경우 입력을 모두 받은게 맞는지 확인하는 습관을 가지자
코드 1
//난이도 : 실버1
//시작 : 18:10
//끝 :
#include <iostream>
#include <vector>
using namespace std;
//MBTI를 숫자로 바꾸는 함수
vector<int> change_num(string tmp) {
vector<int> num_mbti;
if (tmp[0] == 'E') {
num_mbti.push_back(1);
}
else {
num_mbti.push_back(2);
}
if (tmp[1] == 'N') {
num_mbti.push_back(1);
}
else {
num_mbti.push_back(2);
}
if (tmp[2] == 'F') {
num_mbti.push_back(1);
}
else {
num_mbti.push_back(2);
}
if (tmp[3] == 'J') {
num_mbti.push_back(1);
}
else {
num_mbti.push_back(2);
}
return num_mbti;
}
//3개의 MBTI의 거리를 출력하는 함수
int get_distance(vector<vector<int>> mbti_3) {
int distance = 0;
for (int i = 0; i < 4; i++) {
distance += abs(mbti_3[0][i] - mbti_3[1][i]);
}
for (int i = 0; i < 4; i++) {
distance += abs(mbti_3[1][i] - mbti_3[2][i]);
}
for (int i = 0; i < 4; i++) {
distance += abs(mbti_3[0][i] - mbti_3[2][i]);
}
return distance;
}
// 경우의 수에 따라 거리 측정하는 함수
int solve(vector<vector<int>> mbti) {
int min_distance = 100;
for (int i = 0; i < mbti.size() - 2; i++) {
for (int j = i + 1; j < mbti.size() - 1; j++) {
for (int k = j + 1; k < mbti.size(); k++) {
vector<vector<int>> mbti_3;
mbti_3.push_back(mbti[i]);
mbti_3.push_back(mbti[j]);
mbti_3.push_back(mbti[k]);
int distance = get_distance(mbti_3);
if (min_distance > distance) { //최소값 찾기
min_distance = distance;
}
}
}
}
return min_distance;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N;
cin >> N;
vector<vector<int>> mbti;
for (int j = 0; j < N; j++) { //MBTI 입력 받기
string tmp;
cin >> tmp;
mbti.push_back(change_num(tmp));
}
if (N >= 33) { //33개이상인 경우 반드시 거리가 0이다. MBTI의 종류가 16개이기 때문에 최대한 멀게 하려고 해도 중복되는 3개가 존재하기 때문이다.
cout << 0 << '\n';
}
else { //32개 이하인 경우 최소 거리 측정
int min_distance = solve(mbti);
cout << min_distance << '\n';
}
}
return 0;
}코드 2
//난이도 : 실버1
//시작 : 18:10
//끝 :
#include <iostream>
#include <vector>
using namespace std;
//두 MBTI의 거리를 출력하는 함수
int get_distance(string a, string b) {
int distance = 0;
for (int i = 0; i < 4; i++) {
if (a[i] != b[i]) { //문자가 다를경우 거리 +1
distance += 1;
}
}
return distance;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int i = 0; i < T; i++) {
vector<string> str;
int N;
cin >> N;
for (int j = 0; j < N; j++) { //MBTI를 입력 받는다.
string tmp;
cin >> tmp;
str.push_back(tmp);
}
if (N > 32) { //받은 MBTI개수가 32개를 넘는 경우 아무리 거리를 멀리 하려고 해도 MBTI는 16 종류이기 때문에 반드시 3개가 중복되는 것이 발생한다.
//이 때는 거리가 무조건 0이기 때문에 거리를 측정할 필요가 없다.
cout << 0 << '\n';
}
else { //32개 이하이면 다양한 거리가 나올 수 있기 때문에 최소 거리를 직접 계산한다.
int min_distance = 100;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) { //최소 값 찾기를 한다.
min_distance = min(min_distance, get_distance(str[i], str[j]) + get_distance(str[j], str[k]) + get_distance(str[i], str[k]));
}
}
}
cout << min_distance << '\n'; //최소 거리 출력
}
}
return 0;
}🌟 비둘기집 원리
정의
n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리
증명
- n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정한다.
- 만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기 집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리 이므로, 이것은 모순이다.
- 다라서 어느 비둘기 집에는 두 마리 이상의 비둘기가 있다.
용례
- 소프트볼을 하고 싶어하는 5명의 사람이 있다고 할 때, 서로 같은 팀에서 경기를 하고 싶어하지 않지만 팀은 4개 뿐인 경우를 생각해볼 수 있다. 만약 이 사람들이 서로 다른 팀에 들어가고 싶어할 경우, 비둘기집의 원리에 의해 5명의 사람을 한 팀에 한 명씩 4개의 팀으로 나누는 것은 불가능하다는 것을 알 수 있다.
- 해시 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다. 따라서 어떤 해시 함수도 충돌을 피할 수는 없다. -해시 충돌 참고
- 모든 파일을 임의의 크기 S 이하로 압축하는 비손실 압축 알고리즘은 존재하지 않는다. S 이하의 크기를 갖는 파일의 개수는 정해져 있으므로, 그런 알고리즘이 존재한다면 동일한 파일로 압축되는 두 개의 서로 다른 파일이 반드시 존재할 것이므로 두 파일을 다시 원래대로 복원하는 것이 불가능할 것이다.
- 어느 그룹에 생일이 같은 사람이 반드시 1쌍 이상 존재한다고 말할 수 있으려면, 그 그룹의 인원은 367명 이상이어야 한다. 생일의 경우의 수는 2월29일을 포함하여 366가지 이기 때문이다.
- 앞이 보이지 않는 방에서 4쌍의 다른 양말이 널려 있을 때, 5개 이상의 양말을 고르면, 반드시 양말의 짝을 맞추어 신을 수 있다.
- 13명의 사람들 중 태어난 달이 같은 사람이 최소 2명이상 있다.
