[백준 1016, 4948, 17390] - Python
취알스 9주차 기타 알고리즘 - 3/5
1016 제곱 ㄴㄴ 수
1-2년 전에 틀렸던 문제를 드디어 풀었다 ㅋ.ㅋ
import sys
input = sys.stdin.readline
MIN, MAX = map(int, input().split())
array = [True] * (MAX-MIN+1) # 주의
count = 0
n = 2
while n * n <= MAX:
square = n*n
j = MIN // square
while square *j <= MAX:
index = square * j -MIN
if index >= 0 and array[index]:
count +=1
array[index] = False
j+=1
n+=1
print(MAX-MIN+1-count)
주의
array = [True for i in range(MAX+1)]
MAX 값이 최대 1,000,000,000,000 + 1,000,000이기 때문에 메모리 초과가 발생할 수 있음.
4948 베르트랑 공준
import sys
import math
input = sys.stdin.readline
primeNo = [True for i in range(246913)]
for i in range(2, 246913):
if primeNo[i] == True:
j = 2
while i * j <= 246912:
primeNo[i * j] = False
j += 1
while True:
n = int(input())
if n==0:
break
ans = 0
for i in range(n+1, 2*n + 1):
if primeNo[i]:
ans += 1
print(ans)
주의
매 입력마다 소수를 새로 구하면 시간초과 발생
17390 이건 꼭 풀어야 해!
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
arrSum = [0]*(n+1)
for i in range(n):
arrSum[i]=arrSum[i-1]+array[i]
for i in range(m):
l, r = map(int, input().split())
print(arrSum[r-1]-arrSum[l-2])
Author And Source
이 문제에 관하여([백준 1016, 4948, 17390] - Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bb2sol/백준-1016-4948-17390-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)