[백준] 1016번 : 제곱 ㄴㄴ 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1016번: 제곱 ㄴㄴ 수

 

1. 문제 설명

2. 풀이과정

min의 최댓값이 1,000,000,000,000으로 매우 큰 것 같지만 실제로는 min과 max 사이의 수들 안에서 제곱이 아닌 수를 구하는 것이므로 최대 1,000,000의 데이터만 확인하면 된다.

제곱수 판별을 일반적인 반복문으로 구하면 시간 초과가 발생하므로 에라토스테네스의 체 알고리즘 방식을 제곱수 판별할 때 적용해 문제를 해결한다.

 

2의 제곱수인 4부터 max 값까지 제곱수를 찾는다.

제곱수를 찾을 시작 인덱스의 위치는 최솟값 / 제곱수로 정하고 만약 나머지가 0이 아니면 1을 더해준다.

제곱수를 값으로 찾는 것이 아니라 개수만 구하면 되기 때문에 인덱스의 위치를 활용해 제곱수의 배수 형태로 찾는다.

제곱수가 max 값을 넘으면 해당 제곱수를 찾는 반복문을 종료한다.

데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색해 시간 복잡도를 최소화하는 것이 해당 문제를 푸는데 핵심이다.

 

슈도코드

1. min(최솟값), max(최댓값) 입력받기
2. li(min ~ max 사이에 제곱수를 판별할 리스트)
3. for i = 2 ~ max의 제곱근:
   1. pow(제곱수)
   2. start_index(최솟값 / 제곱수)
   3. 만약 최솟값 / 제곱수의 나머지가 0이 아니면 start_index에 1을 더한다.
   4. for j = start_index ~ 최댓값 / 제곱수 사이 반복: j * pow - min이 범위 안의 제곱수이므로 li 리스트에 저장
4. 제곱수가 아닌 수의 개수를 세어 출력

반응형

3. 소스코드

import sys
import math

min, max = map(int, sys.stdin.readline().split())

li = list(False for _ in range(min, max + 1))
for i in range(2, int(math.sqrt(max)) + 1):
    pow = i ** 2
    start_index = int(min / pow)
    if (min % pow != 0):
        start_index += 1
    
    for j in range(start_index, int(max / pow) + 1):
        li[int((j * pow) - min)] = True

print(li.count(False))