[BEAKJOON] 백준 1016번 : 제곱 ㄴㄴ 수

문제 : https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

---

문제 설명

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다.

제곱수는 정수의 제곱.

 

min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

 

 

삽질?

[첫번째 삽질(원초적)] - 알고리즘 분류중에서 에라토스테네스의 체를 보고 처음에는 하나씩 지워가면 되겠다. 제곱수를 카운트를 하자 해서 내가 생각한 제곱수를 카운트해서 빼보자! 했었는데, 예외처리 등을 하나씩 다 생각해줘야 됐어서 아닌 것 같아서 패스

 이런 식으로..

for i in range(min, max+1):
  if(i%4==0):
    count = count + 1
  elif(i%9==0):
    count = count + 1
  elif(i%25==0):
    count = count + 1
  elif(i%49==0):
    count = count + 1
  elif(i%100==0):
    count = count + 1
    
# 4의 배수 지움,
# 9의 배수 지움
# 25의 배수 지움
# 49의 배수 지움

 

[두번째 삽질]

 

제곱수 세기를 count = count + 1로 중복처리를 생각 안하고 진행

-> 중복으로 카운트 되는 수가 있다는 것을 깨달음

=> 리스트에 값을 넣어서 해당되는것에만 1, 아니면 0을 넣어야 겠구나

 

프로세스

0. min과 max를 띄어쓰기를 기준으로 입력 받는다.

 

arr = int,input().split()
# 띄어쓰기 기준으로 나누기 위해서 input()으로 문자열을 입력받고
# arr[0]에는 해당 값의 자료형
# arr[1]에는 값들이 배열로 들어가 있어서 arr[1][0]과 arr[1][1]로 값 할당
min = int(arr[1][0])
max = int(arr[1][1])

 

1. 처음 리스트에 max-min+1 의 크기만큼의 리스트를 0으로 채워놓는다.(중복 카운트 제거)

 

list = [0 for i in range(max-min+1)]

 

2. i가 2부터 제곱수가 max보다 작을 때까지 for문을 돌려준다. (for안에 조건 넣는거 있던데,,)

 

for i in range(2, max):
  if i*i > max:
    break

 

3. 그 안에 j가 min//i의 제곱부터 max까지 range를 돌려준다.

 

3.1. 만약 i*i*j 가 min보다 작으면 다시 continue해줘서 j를 하나 증가시켜서 다시 확인

 

3.2. i*i*j==0 일때도 마찬가지

 

3.3. 만약 i*i*j가 max보다 작거나 같을 때에는 list의 i*i*j-min의 위치를 1로 바꿔준다. (min이 고정되어 있지않기 때문에 list에 min이 0의 위치를 놓아주기 위해서 min을 빼준다.)

 

3.4. i*i*j의 값이 max보다 커지면 중단

 

  for j in range(min//(i*i), max):
    if(i*i*j < min):
      continue
    elif(i*i*j==0):
      continue
    elif(i*i*j <= max):
      list[i*i*j-min] = 1
    else:
      break

 

4. max-min-sum(list)+1을 출력해준다.

 

print(max-min-sum(list)+1)

 

max-min+1 : 숫자 사이의 크기

sum(list) : list에 1인 값(제곱ㄴㄴ수가 아닌 것)을 모두 더해주기

 

---

최종 코드

arr = int,input().split()

min = int(arr[1][0])
max = int(arr[1][1])

list = [0 for i in range(max-min+1)]

for i in range(2, max):
  if i*i > max:
    break
  for j in range(min//(i*i), max):
    if(i*i*j < min):
      continue
    elif(i*i*j==0):
      continue
    elif(i*i*j <= max):
      list[i*i*j-min] = 1
    else:
      break

print(max-min-sum(list)+1)