〈인기투표〉 문제 출제자 해설
〈인기투표〉 문제 출제자 해설
〈2023 전남대학교 PIMM 알고리즘 파티〉 대회 출제분
우리는 백분율을 나타내는 어떤 수에 대해서, 이들 백분율이 나타내는 원래의 모수 $N$을 간단히 추측해내곤 합니다. 문제에서 제시한 상황과 같이, 투표수가 그리 커 보이지 않는 SNS 상의 투표에 대해서는, 저도 이따금 무심코 전체 투표자 수를 계산해보는 일이 있습니다.
풀이
두 개 이상의 정수가 주어졌을 때, 이 정수들을 정수들의 최대공약수로 나눕니다. 이 행위를 ‘이들 수가 공유하는 값을 제거한 것’으로 이해할 수 있습니다. 이렇게 주어진 정수들의 비율 관계를 만족하는 최소의 정수를 획득할 수 있습니다. 다시 말해 획득한 수는 주어진 수 사이의 비율 관계를 최소 정수로 나타냅니다. 백분율에서 유추할 수 있는 모든 투표수는 이 획득한 수의 배수입니다.
이전 시점의 투표에 대해서는, 투표수의 최소 정수를 그대로 출력하여도 무방합니다. 하지만 현재 시점의 추정 값은 그대로 출력하면 안 됩니다. 투표는 철회하거나 번복할 수 없다는 조건이 주어져있으므로, 각 항목의 투표수는 각각 현재 시점이 이전 시점보다 항상 크거나 같아야 합니다.
즉 다음의 출력은 틀렸습니다.
입력
1
2
3
2 0
10 90
50 50
출력
1
10 2
정리하면 이전 시점의 투표수는 입력받은 수들을 이 수들의 최대공약수로 나눈 수입니다. 그리고 현재 시점의 투표수는 “각 항목의 투표수가 이전 시점보다 크거나 같은”, “현재 시점의 수들의 최대 공약수로 나눈 수의 배수”입니다.