[BOJ/Python3] 1206번 : 사람의 수

https://www.acmicpc.net/problem/1206

---

알고리즘 유형

- 브루트포스 알고리즘

문제

송유진은 길거리에서 사람들에게 설문조사를 하고 있다. 설문조사에는 N개의 문항이 있고, 설문에 응한 사람은 각 문항을 0보다 크거나 같고, 10보다 작거나 같은 정수로 대답해야 한다.

설문조사를 모두 마친 후 유진이는 각 문항의 평균 점수 소수점 셋째 자리에서 자른 값을 보고서 종이에 적고 사무실로 돌아왔다. 예를 들어, 어떤 문항에 각 사람이 점수를 4, 6, 10점으로 대답했다면, 평균 점수는 6.666이다. 이제 설문조사 결과를 보고해야 하는데, 문제가 하나 생겼다. 평균 점수만 알고 있기 때문에, 설문조사에 참여한 사람의 수를 알 수 없다는 점이다.

각 문항의 평균 점수가 주어진다. 이때 설문조사에 참여한 사람의 수를 구해보자.

입력

첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 각 문항의 평균 점수가 주어진다. N은 50보다 작거나 같은 자연수이고, 평균 점수는 0보다 크거나 같고, 10보다 작거나 같은 소수이다. 항상 소수점 셋째자리 까지 주어진다.

출력

첫째 줄에 설문조사에 참여한 사람의 수를 출력한다. 만약, 가능한 정답이 여러가지라면, 가장 작은 값을 출력한다.

예제 입출력

---

풀이

예제 입출력 1과 2까지를 보면, 최소공배수. LCD로 풀 수 있다고 생각할 수 있으나 예제 3, 4에 의해 반박된다.

그러므로 이 문제를 풀기 위해서는, 평균을 소숫점 셋째자리 이후 내림한 값 임을 사용해야 한다. 그러므로 아래와 같이 표현할 수 있다.

Ai = < (i번째 문항에 대한 응답의 총합)/M <Ai+0.001 (이 때, 0 =< i번째 문항에 대한 응답의 총합 =< 10*M)

즉, Ai*M =<  i번째 문항에 대한 응답의 총합 < (Ai+0.001)*M 가 되야 하며, 이 구간내에서 정수가 최소한 하나가 있게하는 M을 찾아야 한다. 이 때, 이 수는 N개의 케이스를 모두 만족하게 하면 된다. 그러므로 M을 1씩 증가시키며 브루트 포스 알고리즘, 완전 탐색으로 풀 수 있다.

코드

import math
import sys

N = int(input())
scores = []
M=1

for _ in range(N):
    score_str = sys.stdin.readline().rstrip()
    int_p, de_p = score_str.split('.')
    p = int(int_p) * 1000 + int(de_p)
    scores.append(p)
    
while True:
    ans = True
    # p*M/1000 <= S_i < (p+1)*M/1000
    for p in scores: # left < right 이면 정수가 1개 이상 존재
        left = math.ceil(p * M / 1000)
        numerator = (p + 1) * M - 1
        right = numerator // 1000 
        if left > right:
        	# 구간 내 정수가 없음
            ans = False
            break
    if ans:
        print(M)
        sys.exit()
    M += 1 # 정답이 나올때 까지 +1

---