백준 1016 제곱ㄴㄴ수 풀이 Python

 

문제로이동

1016번: 제곱 ㄴㄴ 수

---

 

---

문제 설명

에라토스테네스의 체 응용 문제입니다.

최대 범위는 1백만, 최대 수는 1조이기 때문에 정수형(long long)과 시간초과에 주의해야 합니다.

 

제곱 수로 나누어 떨어지지 않을 때 제곱ㄴㄴ수라 한다.

제곱수는 아시다시피 아래와 같습니다.

 

2*2 = 4
3*3 = 9
4*4 = 16
...

 

에라토스테네스의 체는 아래와 같습니다.

 

출처 : 위키백과

 

단순하게도 특정 범위에서 제곱수를 에라토스테네스의 체로 걸러내는 방식을 구현하면 됩니다.

 

즉, 2의 제곱인 4의 배수를 걸러내고

3의 제곱인 9의 배수를 걸러내고

4의 제곱인 16의 배수를 걸러내면 됩니다.

 

MIN과 MAX의 크기가 최대 1조 ~ 1조1백만까지 가능하나, 우린 1백만에 초점을 맞춰야 합니다.

 

즉, 수의 크기가 크던 작던 최대 1백만 범위만 신경쓰면 됩니다.

 

해결방법

우선 에라토스테네스의 체를 사용하기 위해 Boolean 형태의 배열을 선언해 줍니다.

MAX-MIN+1을 하면 필요한 공간만큼 생성됩니다. (MIN과 MAX값 모두 포함한 범위이기 때문에 +1이 됩니다)

 

이후 제곱수의 배수를 해당 Boolean 배열에서 체크해 줍니다.

 

단, MIN이 1에서 시작하지 않을 수 있기 때문에 -MIN 연산을 꼭 해주셔야 합니다.

만약 위와 같은 연산을 하지 않는다면 MIN이 1천만일 때 check[1천만]에 접근하게 되므로

check[1천만-MIN] 연산을 해줍니다.

 

체크된 수는 제곱수로 나누어 떨어진다는 뜻이며 제곱ㄴㄴ수에 해당되지 않습니다.

 

2의 제곱수인 4의 경우
MIN보다 같거나 크며, MAX보다 작거나 같은 4의 배수를 모두 제외합니다.

EXAMPLE
MIN = 10, MAX = 16인 경우
2의 제곱수인 4의 배수 (4, 8, 12, 16) 제거
3의 제곱수인 9의 배수 (9, 18) 범위 초과로 반영 X
4의 제곱수인 16의 배수 (16) 제거 (이미 2의 제곱수에서 반영되었으므로 반영 X)

 

 

여기서 로직이 이해되셨을거라 생각하고 remain 변수에 대해 설명하도록 하겠습니다.

MIN = 5, MAX = 10 이라고 가정하겠습니다.

 

당연하게도 여기서 2의 제곱수인 4는 체크할 필요가 없겠죠? 범위가 벗어나기 때문에 범위에 포함되는 요소만 체크해주면 됩니다.

이것을 remain을 이용해 처리해 줍니다.

 

4*1 = 4

4*2 = 8

 

8이 반영되어야 합니다.

 

일일이 1배수부터 증가시켜 조건문을 통해 검증해줘도 되지만 우린 좀 더 편리한 방법을 사용하겠습니다.

 

제곱수에 몇을 곱해야 범위에 들어갈까?

최소값인 MIN에 모듈러 연산을 통해 딱 나누어 떨어진다면 MIN값과 동일할 것이고 그렇지 않다면 MIN보다 작거나 크다는 뜻입니다.

우리에게 필요한 것은 배수(j)가 MIN보다 같거나 커야합니다.

 

 

간단하게도, MIN에 제곱수를 나눈 몫 + 0 또는 1을 해주게 되면 원하는 값을 도출할 수 있습니다.

0 또는 1을 판단하는 방법은 나머지가 조금이라도 있다면 +1을, MIN과 동일한 값이라면 0을 더해주면 됩니다.

 

[EXAMPLE1]
MIN=5,MAX=10

2의 제곱수 4
MIN//4 = 1
MIN%4 = 1이므로
배수는 1(몫)+1(보정) = 2가 됩니다.

즉 5보다 큰 4의 배수인 4*2 = 8이 나오게 됩니다.

 

[EXAMPLE2]
MIN=11,MAX=20

2의 제곱수 4
MIN//4 = 2
MIN%4 = 3이므로
배수는 2(몫)+1(보정) = 3가 됩니다.

즉 11보다 큰 4의 배수인 4*3 = 12가 나오게 됩니다.

---

소스 코드

Python

import sys
input = sys.stdin.readline
def solution(MIN,MAX):
    answer = MAX-MIN+1
    check = [False]*(MAX-MIN+1)
    i=2
    while i*i <= MAX:
        square_number = i*i #제곱수
        # remain
        # 제곱수가 딱 나누어 떨어지면 상관없지만 그게 아니라면 소수점이 버림 처리 된다.
        # 그래서 remain으로 그 값을 보정해준다.
        remain = 0 if MIN%square_number==0 else 1
        j = MIN//square_number + remain #제곱수로 나눈 몫 => 배수
        while square_number*j <= MAX:   #제곱수의 j배 (에라토스테네스의 체)
            if not check[square_number*j-MIN]:
                check[square_number*j-MIN]=True
                answer-=1
            j+=1#배수 점점 증가
        i+=1        
    print(answer)
a,b = map(int,input().split())
solution(a,b)

---

Java8

#