Google Kickstart 2019 Round G – ‘Book Reading’ 풀이

Posted on by

이 포스팅에서는 Google Kickstart 2019 Round G 의 1번 문제인 ‘Book reading’의 풀이와 코드를 제공합니다.
본 풀이는 공식적인 풀이와 완벽히 일치하지 않을 수 있으며, 온라인 Submission을 통과하였습니다.
공식 풀이 및 자세한 사항은 공식 페이지를 참조하세요.

Prob A – Book Reading

문제 정보

문제 링크 : https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02/000000000018fd0d
카테고리 : Divisor
난이도 : 쉬움

문제 설명

N개의 페이지로 구성된 책이 있다.
이 책에서 M개의 페이지는 이미 찢어져 있다.
Q명의 사람들이 이 책을 빌려서 읽으려고 한다.

Q명의 사람들은 각각 R_i의 배수의 페이지를 읽는다.
만약 총 페이지 수가 10이고, R_i이 3이면 그 사람은 3, 6, 9 페이지를 읽는다.

모든 사람들이 읽은 페이지의 총 수를 구하여라

예제 케이스
1
11 1 2
8
2 3

결과 : 7

첫 번째 사람은 2, 4, 6, 10 페이지를 읽는다.
두 번째 사람은 3, 6, 9 페이지를 읽는다.
따라서 총 페이지 수는 7개다.

문제 풀이

Divisors – O(M * sqrt(N))

각각의 P에 대해 약수를 구한다.
이 방법은 sqrt(P)의 시간으로 구할 수 있다.
모든 M개의 P_i에 대해 구하는 시간은 O(M * sqrt(N))이다.
정수 배열 divisors를 만들어서 구해지는 약수 i에 대해 divisors[i] +=1을 해준다.
이 배열은 해당 i에 대해서 i의 배수 중에서 찢어진 페이지의 수를 나타낸다.

모든 R_i에 대해서 N // R_i는 R_i의 배수이며 N보다 작은 모든 페이지의 수를 나타낸다.
여기에 divisors[R_i]를 뺀 값은 찢어지지 않은 페이지의 수를 나타낸다.
이 값을 다 더하면 원하는 값을 구할 수 있다.

코드
def setDivisors(N, divisors):
    for i in range(1, min(N + 1, int(N ** 0.5 + 1))):
        if N % i == 0:
            divisors[i] += 1
            if (N / i) != i:
              divisors[N / i] += 1

T = int(raw_input())
for tt in range(1, T + 1):
    N, M, Q = [int(x) for x in raw_input().split()]
    P = [int(x) for x in raw_input().split()]
    R = [int(x) for x in raw_input().split()]
    divisors = [0] * (N + 1)

    for p in P:
        setDivisors(p, divisors)
    
    Sum = 0
    for r in R:
        Sum += (N // r) - divisors[r]
    print "Case #" + str(tt) +": " + str(Sum)

Competition Kickstart ‘Book reading’