백준/ Gold 1문제 , 백준 파이썬 1016 , 제곱 ㄴㄴ 수
Check Point ! ( 해당사항 ✓체크 )
1. 막힘 없이 수월하게 풀린 문제인가?
2. 1시간이내로 풀렸던 문제인가?
3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?
4. 시간을 써도 도무지 풀 수 없는 문제인가?
5. 솔루션을 찾아봤는가?
-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하
<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함
<덧붙일 말>
에라토스테네츠를 알아보다가 알게된 문제인데 최대한의 수 범위가 ㅎㄷㄷ 하다..
그래도 패턴을 알면 어찌저찌 풀어볼만한 문제이다.
<문제 출처>
https://www.acmicpc.net/problem/1016
1016번: 제곱 ㄴㄴ 수
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수
www.acmicpc.net
------------------------------------------------------------------------------------------------------------------------------
우선적으로 선언할 코드이다.
문제에서 붙여준 이름대로 min, max 를 부여했다
check 리스트에는 확인해야할 수의 범위 만큼 1을 각 자리에 부여한다.
이제 문제를 풀어줄 함수를 선언한다.
1 보다 큰 제곱수부터가 해당 되기때문에 valid 라는 값에 2를 선언한다.
이 값은 while 문을 통해서 계속 값이 변경될 것이다.
while valid**2 <= max:이 코드를 통해 max 이하에 해당하는 제곱수들을 계속 돌려준다.
share = min // valid**2 # 제곱수의 배수들을 확인하기 위해 최소 몫을 구함
while share * (valid**2) <= max:
이 코드가 약간 헷갈릴 수도 있다.
한번 예를 들어보자.
min 값이 20 이고 valid 값이 2 일때
share == 5 의 값이 선언된다.
max 가 만약 100이라면
share * (valid**2) <= max:
5 * 4 <= 100 의 범위에 해당한다.
이제 4라는 제곱수의 배수들은 다 제거 하는 에라토스테네츠의 방식을 이용하면 된다.
if (share * (valid**2)) - min <= max and (share * (valid**2)) - min >= 0:
check[(share * (valid**2) - min)] = 0
이 if 문을 통해 해당 숫자의 check 인덱스값에 0을 부여하고
share+=1 을 통해 4라는 제곱수의 배수를 확인한다.
6 * 4 <= 100 에 해당하기때문에
이부분도 0으로 바꿔줄 수 있다.
이 루틴을 반복하면서 배수들을 0으로 다 바꿔주면 된다.
while 문을 나오면 vaild+=1 을 통해 다음 제곱수를 이제 확인해준다.
이 모든 과정을 반복하여 거친 뒤
최종적으로 남은 수들에는 1의 값이 남아있기때문에
print(check.count(1))
count 를 통해 1의 갯수를 세주면 된다. 어차피 1의 갯수를 세기만하면 되기때문에 sum 을 써도 답은 같다.
------------------------------------------------------------------------------------------------------------------------------
정답
