BOJ 1016 제곱ㄴㄴ수

제곱ㄴㄴ수

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다.
제곱수는 정수의 제곱이다. min과 max가 주어지면,
min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 min과 max가 주어진다.
min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고,
max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

예제 입력

1 10

예제 출력

7

풀이

제곱ㄴㄴ수란

1보다 큰 재곱수로 나누어 떨어지지 않는 수를 의미한다.
1에서 10사이의 제곱ㄴㄴ수는 1,2,3,5,6,7,10이 있다.
4는 제곱수인 4스스로 나누어 떨어 지기 때문에 제곱ㄴㄴ수가 아니고
8은 제곱수인 4로 나누어 떨어 지기 때문에 제곱ㄴㄴ수가 아니며
9는 제곱수인 9스스로 나누어 떨어지기 때문에 아니다.

유의사항

• min과 max의 최댓값은 1조다.

  • 수 하나하나 제곱수로 나누어 떨어지는지 검사하면 시간초과

• max - min의 값의 최대는 100만이다.

  • 하나하나 검사하는 방법을 사용할 수 없다.
  • 배열을 사용해서 해결할 수 있다.

알고리즘

• 1은 무조건 제곱ㄴㄴ수다.
• 제곱수의 배수는 모두 제곱ㄴㄴ수가 아니다.
• 이미 확인한 수는 한번 더 확인하지 않아도 된다.

알고리즘 흐름 (글)

[min(1), max(10)]

초기의 num리스트

[True, True, True, True, True , True, True, True, True, True]

초기의 count값은 10이다.

1. 첫 제곱수인 4부터 반복
   

   • square변수의 값은 4
     
   • i변수의 값은 0
2. 초기 idx변수의 값은 -1로 조건 False
3. i변수의 값 증가로 현재 i의 값은 1
4. idx변수의 값은 3
5. 조건 idx >= 0 and num[idx]가 True

6. count변수 감소, num[idx]값 False로 변경

   • 제곱ㄴㄴ수가 아닌 4를 찾은 경우
7. i변수의 값 증가로 현재 i의 값은 2
8. idx변수의 값은 7

9. 7번 8번과정과 동일

   • 제곱ㄴㄴ수가 아닌 8을 찾은 경우

10. i변수의 값 증가로 현재 i의 값은 3

    • square * i = 12로 안쪽 loop조건 False로 탈출

현재 num리스트의 상태

[True, True, True, False, True , True, True, False, True, True]

제곱수 4의 배수인 4와 8이 걸러졌다.
현재 count의 값은 8이다.

다음 바깥쪽 loop진행

1. 현재 n의 값은 3 제곱수 9로 반복

   • square변수의 값은 9
     
   • i변수의 값은 0
2. 초기 idx변수의 값은 -1로 조건 False
3. i변수의 값 증가로 현재 i의 값은 1
4. idx변수의 값은 8
5. 조건 idx >= 0 and num[idx]가 True

6. count변수 감수, num[idx]값 False로 변경

   • 제곱ㄴㄴ수가 아닌 9를 찾은 경우

7. i변수의 값 증가로 현재 i의 값은 2

   • square * i = 18로 안쪽 loop의 조건 False로 탈출

현재 num리스트의 상태

[True, True, True, False, True , True, True, False, False, True]

제곱수 9의 배수인 9 걸러졌다.
현재 count의 값은 7이다.

현재 n의 값은 4로 바깥쪽 loop의 조건인
n ** 2 <= max를 n ** 2의 값이 16으로 max값인 10보다
커지게 되므로 바깥쪽 loop도 탈출하며 알고리즘 종료

[1, 10]사이의 제곱ㄴㄴ수는 7개가 된다.

알고리즘 흐름 (그림)

글로만 보니 좀 복잡한거 같아 표로 그림을 그려보도록 하겠다.

다음과 같은 초기의 배열이 있다고 하자.
여기에서 제곱수 4의 배수들을 모두 지워주는 것이다.

4의 배수를 모두 지운 후 다음 제곱수인
9의 배수를 모두 지워 주면 된다.

이렇게 되면 제곱ㄴㄴ수만 남게 된다.
소수 판별 알고리즘인 에라토스테네스의 체와 비슷하다.
에라토스테네스의 체를 잘 모르면 여기를 참고하면 된다.

코드 구현부

import sys

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

num = [True for _ in range(min, max + 1)]
count = len(num)
n = 2

while n ** 2 <= max:
    square = n ** 2
    i = min // square

    while square * i <= max:
        idx = square * i - min

        if idx >= 0 and num[idx]:
            count -= 1
            num[idx] = False

        i += 1
    n += 1

print(count)

결과

느리고.. 느리고.. 느렸다..
채점하는데도 진짜 2분은 더 걸린 것 같다..
솔직히 엄청 금방 풀 줄 알았다..
1977번 완전제곱수 문제처럼 Pythonic하게도 짜봐야지~ 했는데…
시간 초과, 메모리 초과의 벽에서 무너졌다😓😓

최근 푼 문제들 중에 제일 힘들었다…😵😵

✅ 코드는 [여기]에서 확인할 수 있다.