[백준] 데이트 (1296번)

문제

오민식은 자기가 좋아하는 여자 N명 중에 한 명과 함께 데이트하러 나가고 싶어한다.

하지만 N명 모두를 사랑하는 오민식에게는 한 명을 선택하고 나머지 여자를 버리는 것은 슬픈 결정이기 때문에 누구를 선택해야 할지 고민에 빠졌다.

마침 오민식은 사랑계산기를 얻었다. 사랑계산기는 두 사람의 이름을 이용해서 두 사람이 성공할 확률을 계산해 준다. 사랑계산기는 다음과 같이 작동한다.

• L = 두 사람 이름에서 등장하는 L의 개수
• O = 두 사람 이름에서 등장하는 O의 개수
• V = 두 사람 이름에서 등장하는 V의 개수
• E = 두 사람 이름에서 등장하는 E의 개수

위의 개수를 모두 계산 한 후에 확률 계산은 다음과 같이 한다.

((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E)) mod 100

오민식의 영어 이름과 나머지 여자들의 이름이 주어졌을 때, 오민식과 성공할 확률이 가장 높은 여자의 이름을 출력하는 프로그램을 작성하시오. 여러명일 때에는 알파벳으로 가장 앞서는 이름을 출력하면 된다.

입력

첫째 줄에 오민식의 영어 이름이 주어진다. 둘째 줄에는 좋아하는 여자가 몇 명인지 N이 주어지고, 셋째 줄부터 N개의 줄에 여자의 이름이 하나 씩 주어진다. N은 50보다 작거나 같고, 모든 이름은 알파벳 대문자로만 구성되어 있고 모두 길어야 20글자이다.

출력

오민식이 선택한 여자의 이름을 출력한다.

예제 입력 1 복사

OHMINSIK 9 YOONA TIFFANY YURI HYOYEON SOOYOUNG SEOHYUN TAEYEON JESSICA SUNNY

예제 출력 1 복사

HYOYEON

---

문제 제목부터 내용까지 로맨틱한 문제다.

민식이의 영어 이름과 상대방의 이름을 합해서 L, O, V, E 총 개수를 구해준다.

그 후 곱셈 연산을 통해 총 점수가 가장 높은 상대방 이름을 출력한다.

점수가 같다면 이름이 사전 순서로 앞서는 사람을 출력한다.

 

이름 출력을 위해 priority queue를 쓰고 cmp 함수를 구현했었는데 생각해보니 쓸데없이 너무 어려운 연산을 쓴 것 같아, 간편하게 매번 대소 비교를 해서 마지막에 결과를 출력했다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%8D%B0%EC%9D%B4%ED%8A%B8%20(1296%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
int N;
string origin, lover;
int l, o, v, e;
int cur, res = -1;
int main()
{
	cin >> origin;
	for (int i = 0; i < origin.size(); i++) {
		if (origin[i] == 'L') l++;
		else if (origin[i] == 'O') o++;
		else if (origin[i] == 'V') v++;
		else if (origin[i] == 'E') e++;
	}

	cin >> N;
	while (N--) {
		int tmpL = l, tmpO = o, tmpV = v, tmpE = e;
		string str;
		cin >> str;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == 'L') tmpL++;
			else if (str[i] == 'O') tmpO++;
			else if (str[i] == 'V') tmpV++;
			else if (str[i] == 'E') tmpE++;
		}
		cur = ((tmpL + tmpO) * (tmpL + tmpV) * (tmpL + tmpE) * (tmpO + tmpV) * (tmpO + tmpE) * (tmpV + tmpE)) % 100;
		if (cur > res) {
			res = cur;
			lover = str;
		}
		else if (cur == res) {
			if (str < lover) lover = str;
		}
	}
	cout << lover;	
}

 

priority queue 버전

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
int N;
string origin;
int l, o, v, e;

struct cmp {
	bool operator()(pair<int, string> a, pair<int, string> b) {
		if (a.first == b.first)
			return a.second > b.second;
		return a.first <= b.first;
	}
};

int main()
{
	cin >> origin;
	for (int i = 0; i < origin.size(); i++) {
		if (origin[i] == 'L') l++;
		if (origin[i] == 'O') o++;
		if (origin[i] == 'V') v++;
		if (origin[i] == 'E') e++;
	}

	cin >> N;
	priority_queue<pair<int, string>, vector<pair<int, string>>, cmp> q;
	while (N--) {
		int tmpL = l, tmpO = o, tmpV = v, tmpE = e;
		string str;
		cin >> str;
		for (int i = 0; i < str.size(); i++) {
			if (str[i] == 'L') tmpL++;
			if (str[i] == 'O') tmpO++;
			if (str[i] == 'V') tmpV++;
			if (str[i] == 'E') tmpE++;
		}
		int res = ((tmpL + tmpO) * (tmpL + tmpV) * (tmpL + tmpE) * (tmpO + tmpV) * (tmpO + tmpE) * (tmpV + tmpE)) % 100;
		q.push({ res, str });
	}
	cout << q.top().second;
}