classe88   5년 전

<코드 첨부>

풀이코드 작성한 것은 위와 같습니다.

구간이 5 - 120이 주어진 경우,

  1. 120미만인 제곱수 중 소수인 것만 구합니다. (2^2, 3^2, 5^2, 7^2), (11^2은 120초과이므로 고려 X)
  2. 위에서 소수를 구하는 경우는 GCD알고리즘을 적용하여, 둘의 최대공약수가 1이 아닌 경우 소수가 아니므로 고려할 제곱수에 포함 X.
  3. 해당 구간에서 각 제곱수의 배수가 몇 개 있는지를 계산합니다. 
  4. (start와 end를 나눈 몫을 활용하여 개수를 계산, 둘 중 하나의 나머지가 0인 경우도 계산함)
  5. 그 제곱수의 배수들을 다 더하고, start -end 사이의 총 숫자 개수에서 빼줍니다.
  6. 그럼 결과는 제곱ㄴㄴ수일 것입니다.

위 풀이에서 5-120인 경우

4의 배수는 4X2 ~4X30이 구간 내에 포함된 제곱수에 해당하므로 29개

9의 배수는 9X1 ~ 9X13이 구간 내에 포함된 제곱수에 해당하므로 13개

25의 배수는 25X1 ~ 25X4이 구간 내에 포함된 제곱수에 해당하므로  4개

49의 배수는 49X1 ~49X2가  구간 내에 포함된 제곱수에 해당하므로 2개

총 48개의 제곱수가 5-120에 존재하고, 5-120에는 116(120-5+1)개의 수가 존재하므로

116-48 = 68. 따라서 제곱ㄴㄴ의 수는 68개.

이렇게 풀었는데요... 그러나 답이되는 알고리즘에서는 5-120의 경우 72개가 나와야 정답판정이 되네요..

어디서 틀린걸까요? 

bupjae   5년 전

4의 배수이면서 9의 배수인 수 (36, 72, 108)

4의 배수이면서 25의 배수인 수 (100)

댓글을 작성하려면 로그인해야 합니다.