백준 25757번 임스와 함께하는 미니게임 C++

백준 25757번: 임스와 함께하는 미니게임 (C++)

문제 설명

임스가 미니게임을 같이할 사람을 찾고 있습니다.

플레이할 미니게임으로는 윷놀이 Y, 같은 그림 찾기 F, 원카드 O가 있습니다. 각각 2, 3, 4 명이서 플레이하는 게임이며 인원수가 부족하면 게임을 시작할 수 없습니다.

사람들이 임스와 같이 플레이하기를 신청한 횟수 N과 임스가 플레이할 게임의 종류가 주어질 때, 최대 몇 번이나 임스와 함께 게임을 플레이할 수 있는지 구하시오.

임스와 여러 번 미니게임을 플레이하고자 하는 사람이 있으나, 임스는 한 번 같이 플레이한 사람과는 다시 플레이하지 않습니다.

임스와 함께 플레이하고자 하는 사람 중 동명이인은 존재하지 않습니다. 임스와 lms0806은 서로 다른 인물입니다.

---

입력

첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 N과 같이 플레이할 게임의 종류가 주어진다.

(1 ≤ N ≤ 100,000)

두 번째 줄부터 N개의 줄에는 같이 플레이하고자 하는 사람들의 이름이 문자열로 주어진다.

(1 ≤ 문자열 길이 ≤ 20)

사람들의 이름은 숫자 또는 영문 대소문자로 구성되어 있다.

---

출력

임스가 최대로 몇 번이나 게임을 플레이할 수 있는지 구하시오.

---

예제 입력 1

7 Y
lms0806
lms0806
exponentiale
lms0806
jthis
lms0806
leo020630

---

예제 출력 1

4

---

예제 입력 2

12 F
lms0806
powergee
skeep194
lms0806
tony9402
lms0806
wider93
lms0806
mageek2guanaah
lms0806
jthis
lms0806

---

예제 출력 2

3

---

문제 작동 원리 (사례 기반)

문제를 해결하는 과정을 실제 입력 사례에 맞추어 풀어보겠습니다.

---

사례 1: 7 Y

입력 이름 목록:

lms0806, lms0806, exponentiale, lms0806, jthis, lms0806, leo020630

• 1. 중복 제거 → lms0806, exponentiale, jthis, leo020630
• 총 인원 = 4명
• 2. 게임 Y는 임스 + 1명 필요. 즉 고유 인원을 1명씩 나누어 쓰면 됨.
• 4 / 1 = 4
• 3. 따라서 가능한 게임 횟수 = 4번

---

사례 2: 12 F

입력 이름 목록:

lms0806, powergee, skeep194, lms0806, tony9402, lms0806, wider93, lms0806, mageek2guanaah, lms0806, jthis, lms0806

• 1. 중복 제거 →
• lms0806, powergee, skeep194, tony9402, wider93, mageek2guanaah, jthis
• 총 인원 = 7명
• 2. 게임 F는 임스 + 2명 필요. 즉 고유 인원을 2명씩 묶어야 함.
• 7 / 2 = 3
• 3. 따라서 가능한 게임 횟수 = 3번

---

사례 3: 8 O

예를 들어 입력이 다음과 같다고 합시다.

a, b, c, d, e, f, g, h

• 1. 중복 제거 후 총 인원 = 8명
• 2. 게임 O는 임스 + 3명 필요. 즉 고유 인원을 3명씩 묶어야 함.
• 8 / 3 = 2
• 3. 따라서 가능한 게임 횟수 = 2번

---

아이디어

• 이름 입력은 중복이 있을 수 있으므로, 반드시 중복 제거가 필요합니다.
• set 자료구조를 이용하면 이름이 자동으로 중복 제거됩니다.
• 최종적으로 고유 인원 수 ÷ (필요 인원 - 1)를 계산하면 됩니다.
• Y → arr.size() / 1
• F → arr.size() / 2
• O → arr.size() / 3

---

전체 코드

#include <iostream>
#include <cstring>
#include <set>
using namespace std;
struct word{
    char arr[100];
    bool operator<(const word& other) const {
        return strcmp(arr, other.arr) < 0;
    }
};
int main(void)
{
    int N;
    char game;
    set<word> arr;
    word st;
    cin >> N >> game;
    for(int i = 0; i < N; i++)
    {
        cin >> st.arr;
        arr.insert(st);
    }
    if(game == 'Y')
        cout << arr.size() << endl;
    else if(game == 'F')
        cout << arr.size() / 2 << endl;
    else if(game == 'O')
        cout << arr.size() / 3 << endl;
    return 0;
}

---

결론

• 게임 종류에 따라 필요한 인원을 기준으로 나눠야 합니다.
• 핵심 공식: 고유 인원 수 ÷ (필요 인원 - 1)
• 실제 사례를 통해 확인해 보면, Y, F, O 모두 이 규칙으로 정확히 계산됩니다.