BOJ 30878 : 약속 시간

• 문제 링크 : boj.kr/30878
• 난이도 : G1
• 태그 : 수학, 확률론

30878번: 약속 시간

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int m;
    cin >> m;
    int ans = m*m*(m + 3*(60-m));
    int b = 60 * 60 * 60;

    cout << ans / gcd(ans, b) << "/" << b / gcd(ans, b);

    return 0;
}

---

풀이

조건을 수식으로 풀어보면 다음과 같다.

• $0 \le x, y, z \le 60$
• $|x-y| \le M, |y-z| \le M, |z-x| \le M$

이 수식을 만족하는 도형의 부피가 세 사람이 만날 확률이다.

 

이 모양을 바로 상상하긴 어려우니 2차원에 투영해보자. 비교적 그림을 쉽게 그릴 수 있다.

이는 한 변의 길이가 M이고 한 꼭짓점이 $(t, t)$, 그 반대쪽 꼭짓점이$(t+M, t+M)$인 정사각형이 있고, $(0 \le t \le 60-M)$일때, 정사각형의 자취와 같다.

마찬가지의 방법으로 3차원에 확장해보면 한 변의 길이가 M이고 한 꼭짓점이 $(t, t, t)$, 그 반대쪽 꼭짓점이$(t+M, t+M, t+M)$인 정육면체가 있고, $(0 \le t \le 60-M)$일때, 정육면체의 자취와 같다.

 

다만 이 자취의 부피를 바로 계산하기에는 어려움이 있다. 쉽게 계산하기 위해, 정육면체 중 $x=t, y=t, z=t$인 세 정사각형의 자취를 먼저 이용해 구할 것이다. 하나의 정사각형만 가지고 상상력을 발휘해보자. 이 정사각형이 그리는 자취가 밑변은 한 변의 길이가 $M$이고, $x=y=z$인 직선을 빗변으로 타고 올라가는 도형임을 알 수 있고, 이 도형의 부피는$ M*M*(60-M)$임을 알 수 있다. 정사각형이 세 개이므로 앞에서 구한 부피에 세 배를 해주고, 처음에 제외했던 정육면체의 부피를 더해주면 앞의 수식을 만족하는 도형의 부피를 구할 수 있다.

 

이제 만날 확률의 부피를 구했으므로, 전체 공간의 부피로 나눠준 다음 각각을 최대공약수로 나누어 주면 된다.