문제
학생들은 3주가 지난 기념으로 매점에서 1월 1일이 지나 싸게 파는 폭죽을 사서 터뜨리고 있다.
폭죽쇼를 하는 동안 N명의 학생들이 폭죽을 터뜨린다. 그리고 이 N명의 학생은 각각 일정한 주기로 폭죽을 터뜨린다. 물론 이 주기는 학생들마다 같을 수도, 다를 수도 있다. 그리고 우리는 초 단위로 관찰을 하고, 폭죽 역시 초 단위로 터진다.
폭죽쇼가 끝날 때까지 얼마나 많은 시간동안 밤하늘에 폭죽이 터지는 것을 볼 수 있는지 궁금해 하는 조교를 도와주자.
입력
첫 줄에 폭죽을 터뜨리는 학생의 수 N(1 ≤ N ≤ 100)과 폭죽쇼가 끝나는 시간 C(1 ≤ C ≤ 2,000,000)가 주어진다. 그 다음 N개의 줄에는 학생들이 폭죽을 터뜨리는 주기가 한 줄에 하나씩 주어진다. 주기는 1보다 크거나 같고, C보다 작거나 같은 자연수이다.
출력
폭죽쇼가 시작되고 끝날 때까지 밤하늘에 폭죽을 볼 수 있는 총 시간을 출력한다.
풀이
시간초과는 참 어렵다..
내 코드
N, C = map(int, input().split())
time = [0] * (C+1)
fire = []
for i in range(N):
fire.append(int(input()))
count = 0
for i in fire:
# print('i=', i)
j = 1
while j * i <= C:
# print(j * i)
if time[j * i] == 0:
time[j * i] = 1
count += 1
j += 1
print(count)폭죽이 끝나는 시간까지 폭죽 주기를 곱하였는데 조건이 C(1 ≤ C ≤ 2,000,000) 이라 시간 초과가 뜨는 것 같다.
참고한 코드
N, C = map(int, input().split())
time = [0] * (C+1)
count = 0
for i in range(N):
fire = int(input())
for j in range(fire, C+1, fire):
if time[j] == 0:
time[j] = 1
count += 1
print(count)이것 역시 python3 로 제출하면 시간초과가 뜬다.
위의 코드, 아래코드 둘 다 PyPy3 로 제출하면 시간초과는 안뜬다. 하지만 python 으로 어떻게 구현해야 시간초과가 안뜰지 고민해봐야 할 것 같다.
