person3113

늙어서 은퇴하기 전까진 계속 공부하자!!


난이도

풀 시도를 했지만 쉬운 것 같은데 어려워서 끙끙 앓다가, 그냥 정답 코드를 봤다. 코드를 봐도 왜 이렇게 했는지 이해하는 데에 약간의 시간이 더 걸렸다.



문제

제곱이 아닌 수 찾기(백준: 1016번)

image



교재 풀이

import java.util.*;

public class MainTest {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    long Min = sc.nextLong();
    long Max = sc.nextLong();
    boolean[] Check = new boolean[(int) (Max - Min + 1)]; // 최대 최소 차이만큼 배열 선언
    // 2의 제곱수인 4부터 max보다 작거나 같은 까지 반복
    for (long i = 2; i * i <= Max; i++) {
      long pow = i * i; // 제곱수
      long start_index = Min / pow;

      // 나머지가 있으면 1을 더해주어야 Min보다 큰 제곱수 부터 시작됨
      if (Min % pow != 0)
        start_index++;
      for (long j = start_index; pow * j <= Max; j++) {
         // 제곱수를 true로 변경
        Check[(int) ((j * pow) - Min)] = true;
      }
    }

    int count = 0;
    for (int i = 0; i <= Max - Min; i++) {
      if (!Check[i]) {
        count++;
      }
    }
    System.out.println(count);
  }
}



풀이 이해

long start_index = Min / pow;
if (Min % pow != 0)
    start_index++;
for (long j = start_index; pow * j <= Max; j++) {
    // 제곱수를 true로 변경
    Check[(int) ((j * pow) - Min)] = true;
}

참고 사이트

  • 예를 들어 min = 30이고, max = 100 이었다고 가정해 보자. 30 이상 100 이하의 숫자 중에서 제곱수 4 = (2*2)로 나누어 떨어지는 가장 작은 숫자를 구할 때는 다음과 같이 하면 된다.

    • min 값인 30을 (2 * 2)로 나눈 몫을 구한다. = 30 / 4 = 7
    • 그 몫에 다시 (2 * 2)를 곱해본다. = 7 * 4 = 28
    • 28은 범위에 속하지 않는 숫자이므로, 7에 1을 더한 8에 (2 * 2)를 곱해 보면 32가 된다.
    • 따라서 제곱수와 곱하여, 가장 작은 수인 32를 만드는 숫자는 8(구하려는 수/start_index)이 된다.
    • 그러므로 8부터 ( 8 * (2 * 2), 9 * (2 * 2), 10 * (2 * 2), … , 25 * (2 * 2) ) = (32, 36, 40, … , 100) 에는 이미 나누어 떨어지는 수라는 표시를 한다.

  • Check[(int) ((j * pow) - Min)] = true;부분에서 인덱스를 왜 ((j * pow) - Min)으로 했는가?

    • 앞 예시에서 쭉 이어오면, pow = 4(2 * 2)이고 j = start_index인 8이 된다. 그럼 (j * pow)는 32가 된다. 하지만 Check[] 배열은 new boolean[(int) (Max - Min + 1)];으로 선언했다. 즉 이 배열에서 32라는 수에 해당하는 인덱스는 32 - Min(30) = 2이다(index = 0 -> 30 / index = 1 -> 31 /index = 3 -> 32). 따라서 인덱스를 위처럼 설정한 것으로 보인다.

참고