이 포스팅에서는 Google Kickstart 2019 Round G 의 1번 문제인 ‘Book reading’의 풀이와 코드를 제공합니다.
본 풀이는 공식적인 풀이와 완벽히 일치하지 않을 수 있으며, 온라인 Submission을 통과하였습니다.
공식 풀이 및 자세한 사항은 공식 페이지를 참조하세요.
문제 링크 : 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’
유럽 여행 2주간 대학 친구와 유럽여행을 다녀왔다. 런던 출장외에 유럽 여행은 완전 처음이었는데, 좋았던 점이…
Layoff 이번 주에 또 한차례 Layoff가 있었다. 작년 1월 대규모 Layoff 이후 1년만의 일이다. 새벽…
2023 회고 큰 성공을 만든 건 없지만, 작년에 달성한 것들을 모아보자면 일단 잘리지 않고 해고를…
영주권 매일 아침 USPS 이메일과 USCIS 앱을 열어보면서 기다리던 영주권이 드디어 발급되었다. 오늘 드디어 새로…
TL;DR 이 일기는 OKR 설정의 어려움, 효과적인 마케팅 전략의 필요성, 가족 중심의 삶과 이민자로서의 경력…
TL;DR 미국 생활에 찾아온 작은 변화와 가족과의 여행 소소한 행복, 그리고 AI 기술의 급속한 발전…
This website uses cookies.