[BOJ C++] 백준 33622번: 새치기하지 마!!!

 📚 문제

[BOJ C++] 백준 33622번: 새치기하지 마!!!
https://www.acmicpc.net/problem/33622

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 걸릴 확률이 가장 낮은 경우를 찾으려다보니 어려웠던 문제이다...😥 걸리지 않는 경우로 바꾸어 계산하는 방법이 훨씬 간단하게 정리된다.
• 재우가 i번째로 사람을 제칠 때 제친 사람의 수를 $k_1, k_2, k_3, ... , k_x$라고 한다. $k_1$부터 $k_x$까지 사람을 제치면 n명의 사람을 모두 제친 것이므로, $k_1+k_2+k_3+...+k_x=n$이다.
• 사람을 제칠 때마다 사람 수($n$)는 $k_1, k_2, k_3, ... , k_x$만큼 줄어드므로 각 경우에서의 확률을 식으로 나타내면 $\frac{k_1}{n+1},$ $\frac{k_2}{n+1-k_1},$ $\frac{k_3}{n+1-k_1-k_2},$ $...$ $,\frac{k_x}{n+1-k_1-k_2-k_3-...-k_{x-1}}$이다.

‼️$\frac{k_1}{n+1}\times\frac{k_2}{n+1-k_1}\times\frac{k_3}{n+1-k_1-k_2}\times...\times\frac{k_x}{n+1-k_1-k_2-k_3-...-k_{x-1}}$가 가장 작은 경우를 구하는 문제라고 오해해서는 안된다. (사실 그게 나야 ㅠ) 첫번째부터 x번째 경우 중 한 번이라도 걸리면 실패이므로 전체 확률(1)에서 한 번도 걸리지 않는 경우의 수를 빼는 것이 적절하다.

 

• 즉, $(1-\frac{k_1}{n+1})\times(1-\frac{k_2}{n+1-k_1})\times(1-\frac{k_3}{n+1-k_1-k_2})\times...\times(1-\frac{k_x}{n+1-k_1-k_2-k_3-...-k_{x-1}})$ 를 계산해야한다.
• 식을 정리해보면,
  $= \frac{n+1-k_1}{n+1}\times\frac{n+1-k_1-k_2}{n+1-k_1}\times\frac{n+1-k_1-k_2-k_3}{n+1-k_1-k_2}\times...\times\frac{n+1-k_1-k_2-k_3-...-k_{x-1}-k_x}{n+1-k_1-k_2-k_3-...-k_{x-1}}$
  $= \frac{n+1-k_1-k_2-k_3-...-k_{x-1}-k_x}{n+1} = \frac{n+1-n}{n+1} = \frac1{n+1}$이 된다.
• 따라서 어떤 방식으로 새치기를 하는지와 관계없이 항상 같은 확률을 유지한다. $k_1+k_2+k_3+...+k_x=n$을 만족하는 아무 수열을 출력하면 된다. 필자는 한 번에 모든 사람을 새치기하는 경우로 출력했다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    cout << 1 << '\n' << n;
}

이상하게 요즘 푸는 문제마다 코드는 간단하고 해결 과정이 복잡한 문제들이 많이 걸리는 것 같다... 너무 간단해서 허무할정도 ㅋㅋㅋㅋㅜㅜ