Kickstart

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

이 포스팅에서는 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’

admin

Share
Published by
admin

Recent Posts

2024년 12월 8일 일요일 – 서울 생활 132주차

합격왕 우여곡절 끝에 드디어 합격왕에 광고를 붙였다. 서비스를 시작한지 무려 4년이 지나서야 드디어 광고를 시작하게…

2주 ago

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

1개월 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

2개월 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

3개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

3개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

3개월 ago

This website uses cookies.