[알고리즘 문제 풀이][수학] 백준 23364번 - Almost Always

백준 23364 Almost Always 문제의 풀이 방법을 정리한 내용입니다.

 

- 문제 설명: https://www.acmicpc.net/problem/23364 

 

1부터 2*10^9 까지 범위의 숫자를 5*10^5 개 뽑습니다. 문제에서 주어지는 n 은 항상 5*10^5로 고정입니다.

이때 n 개의 숫자 중에 한 숫자가 다른 숫자로 나누어 떨어지면 두 숫자의 위치를 답하는 문제입니다. (나누는 수 먼저, 나누어지는 수 나중)

 

예제 입력 1을 보면

10

4 9 8 10 5 28 3 62 9 17 

이 주어집니다.

이 중, 10 을 5로 나눌 수 있으므로 5와 4를 응답합니다.

(예제이기 때문에 n = 10 으로 주어집니다)

 

- 문제 풀이:

이 문제는 Birthday Problem (생일 문제) 를 활용하는 문제입니다.

1년이 365일 일 때, 최소 몇 명이 모여야 생일이 같은 사람이 있을 확률이 50%를 넘을까? 라는 문제에

답은 23명만 모이면 그 중에 생일이 같은 사람이 있을 확률이 50% 이상이 된다 입니다.

 

이를 응용하면, 5*10^5 (50만개) 의 수를 뽑으면 동일한 수가 있을 확률이 매우 높아집니다.

https://measurezero.tistory.com/1029

 

따라서 한 수가 다른 수를 나누는지 볼 필요 없이,

같은 수가 있는지 여부만 확인하는 것으로도 해당 문제를 풀 수 있습니다.

 

[참고] ChatGPT 답변을 참고함

 

확률 계산 방법은 다음과 같습니다.

만약 N 명의 학생이 있을 때 같은 생일이 있을 확률을 구하려면 1에서 아래 P 를 빼면 됩니다.

P(모두 서로 다른 수를 뽑을 확률)=N/N​×(N−1)/N​×(N−2)/N​×⋯×(N−n+1​)/N

365/365*364/365*363/365*... 이런 식입니다. (앞에 학생이 생일을 하나 골랐으면, 뒤에 학생이 그것과 다른 생일일 확률, 그 다음 학생은 앞에 두 생일과 다를 확률...)

이렇게 곱해서 얻는 값은 매우 크므로, 이를 로그를 사용할 수 있습니다.

logP(모두 서로 다른 수를 뽑을 확률)=log(N/N​×(N−1​)/N×⋯×(N−n+1)/N​)

이를 Python 코드를 통해 계산해보면 확률이 1.0 이 나오게 됩니다.

import math

# 주어진 값들
N = 2_000_000_000
n = 500_000

# 로그를 사용하여 계산
log_prob = sum(math.log(1 - k / N) for k in range(n))
prob_different = math.exp(log_prob)

# 적어도 두 수가 같은 수일 확률
prob_same = 1 - prob_different
prob_same

 

 

- 코드 (Python): 

n=int(input())
a=list(map(int, input().split()))
d={}
for i in range(1,n):
    if a[i] in d:
        print(i+1, d[a[i]]+1)
        break
    else:
        d[a[i]]=i

기존에 숫자가 존재하는지 확인하기 위해 python 의 dictionary 를 활용하였습니다.

c++ 이라면 map 을 사용하면 됩니다.

기존에 숫자가 존재하지 않으면 dictionary 에 숫자의 위치를 저장하고,

기존에 같은 숫자가 존재하면 저장된 위치와 현재 위치를 출력합니다.

 

- 실수 포인트 & 반례:

문제의 예제 외에 필요한 반례는 없었습니다