[Algorithm] 백준온라인저지 1016번 Java로 문제 풀이! (BOJ-1016)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 에라토스테네스의 체를 응용한 문제를 한번 풀어보겠습니다.

 

1. 문제 설명

백준 온라인 저지에 있는 1016번 문제 링크는 아래에 있습니다.

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

 

해당 문제는 에라토스테네스의 체를 사용해서 접근을 해야 합니다.

에라토스테네스의 체 알고리즘은 소수 판별에 많이 사용되는데요~

현재 풀려고 하는 문제는 소수를 판별하는 것이 아니라 "제곱ㄴㄴ수"를 판별해야 하기 때문에 에라토스테네스의 체 알고리즘을 소수 판별이 아닌 제곱수를 판별하는 형태로 응용해서 사용해야 합니다.

또한 문제에서 주어지는 수의 범위가 1조 1백만까지 나타나므로 주의해야 합니다

그러면 문제를 한번 풀어보겠습니다.

 

2. Java로 문제 풀이

전체적인 소스코드는 아래와 같습니다.

package study.blog.codingnojam.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_1016 {
    // 백준온라인저지(BOJ -1016) 제곱ㄴㄴ 수 문제풀이
    public static void main(String[] args) throws IOException {

        // 문제에서 주어지는 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] info = br.readLine().split(" ");
        long min = Long.parseLong(info[0]);
        long max = Long.parseLong(info[1]);

        // 제곱ㄴㄴ수 판별에 사용 할 배열
        long[] arr = new long[1000001];

        // 배열에 저장 될 값 초기화를 위해 사용할 변수
        long init = min;

        // 제곱ㄴㄴ 개수 저장 할 변수
        int count = 0;

        // 배열 초기화 (min ~ max까지의 값 배열에 저장)
        for (int i = 0; i < arr.length ; i++) {
            arr[i] = init++;
            if(init == max+1){
                break;
            }
        }

        // 1 이상의 수에서 제곱을 해야 하기때문에 2부터 시작
        // 문제에서 max의 최대값은 1조1백만이므로 백만*백만 까지만 반복하면 됨
        // 1000001 * 1000001은 1조1백만 이상의 값이 나옴
        for (long i = 2; i <= 1000000 ; i++) {
            // 제곱수 계산
            long squareNumber = i * i;

            // 제곱수가 max값 보다 크면 더 이상 반복하지 않음
            if (squareNumber > max) {
                break;
            } else { // 제곱수가 max값 보다 작을 때

                // 제곱수로 나누어떨어지는 가장 작은 값을 찾기 위한 연산 시작
                // min을 제곱수로 나누어서 몫을 구함
                long quot = (min / squareNumber);
                // 구한 몫에 다시 제곱수를 곱해서 그 값이 min보다 작으면 몫에 1을 더함
                if (quot * squareNumber < min) {
                    quot++;
                }
                // 계산된 몫에 제곱수를 곱한 후 min값을 뺴면 배열의 인덱스를 구할 수 있음
                long j = (quot * squareNumber) - min;

                // 배열에 위에서 구한 인덱스의 값을 0으로 변경 (제곱수로 나누어지는 숫자임)
                // 인덱스에 제곱수만큼 더해서 그 다음 인덱스의 값을 0으로 변경 (제곱수의 배수이므로 나누어지는 수임)
                // 배열의 길이보다 커질 때까지 반복
                for (long k = j; k < arr.length; k = k+squareNumber) {
                    arr[(int)k] = 0;
                }
            }
        }
        // 배열에서 제곱 ㄴㄴ수 개수 세기
        for (int i = 0; i < arr.length ; i++) {
            if(arr[i] != 0){
                count++;
            }
        }

        // 출력
        System.out.println(count);
    }
}

코드마다 모두 설명을 달아놓았으니까 문제풀이에 있어서 중요한 코드를 설명드리겠습니다.

 

18~19라인에 배열을 하나 선언하는데 현재 문제에서 수의 개수가 최대 1000001개가 나오므로 배열의 길이도 1000001로 잡아주었습니다.

사실 메모리를 조금 더 효율적으로 쓰기 위해서는 min에서 max까지의 수의 개수를 세서 배열의 길이로 주면 되는데 저는 그냥 편의상 최대길이로 배열을 생성해주었습니다.

 

27~33라인에서는 배열의 값을 초기화해줍니다.

min값부터 시작해서 배열의 끝까지 값을 모두 채워주지 않는 이유는 배열의 값이 0일 때는 "제곱ㄴㄴ수"가 아니라고 판별하기 위해서 min~max까지만 값을 채워줍니다.

max값 이후의 배열의 인덱스들은 primitve타입의 기본값인 0으로 초기화됩니다.

 

38라인의 for문은 2 이상부터 제곱수를 구하기 위해 반복문을 사용했습니다.

 

43~44라인의 if문은 제곱수가 max값보다 크면 나눠봤자 의미가 없기 때문에 클 경우 제곱수를 계산하는 반복문을 종료합니다.

 

48~54라인의 코드는 제곱수로 나누어지는 가장 작은 숫자를 찾는 코드입니다.

왜 제곱수로 나누어지는 가장 작은 숫자를 찾아야 하는가?

예를 들어 배열의 0 인덱스부터 시작해서 1 2 3 4 5 ~~ 등 연달아서 제곱수로 나누어보고 떨어지는 숫자를 찾는다면 시간 초과 판정을 받을 확률이 매우 높습니다.

아마 주어진 숫자가 작다면 시간 초과를 받지 않겠지만 min값이 1조, max값이 1조 1백만 일 경우는 시간 초과를 받습니다.

왜냐면 제곱수를 계산하기 위한 for문이 2부터 100만까지 반복해야 하며(100만*100만=1조), 제곱수마다 1조부터 1조 1백만까지 100만 개의 수를 체크해야 하므로 시간 초과 판정을 받습니다.

조금 더 최적화한다면 처음으로 제곱수로 나누어지는 수의 인덱스를 찾아내고, 해당 인덱스에 제곱수를 계속적으로 더하면서 배열의 값을 변경하는 방법이 있습니다.

그러나 이 방법 또한 처음으로 제곱수로 나누어지는 수를 찾을 때까지 계속 체크해야 하므로 시간 초과 판정을 받습니다.

그러므로 배열에서 처음으로 제곱수로 나누어지는 수를 한 번의 연산으로 찾는 방법을 사용해야 합니다.

절차는 다음과 같습니다.

1. min값을 제곱수로 나누어서 나머지는 버리고 몫만 구함 (min값 / 제곱수 = 몫)

2. 구한 몫에 제곱수를 다시 곱한 후 min값이랑 비교 (몫 * 제곱수 <,>,= min)

3. 2번의 값이 min보다 작다면 몫에 +1 (2번 값 < min -> 몫+1)

4. 2번의 값이 min보다 크거나 같다면 아무것도 안 함

5. 앞의 과정에서 계산된 몫에 제곱수를 곱하고 min값을 빼줌 (몫 * 제곱수 - min)

6. 5번에서 계산된 결괏값이 배열의 원소 중 제곱수로 나누어지는 가장 작은 수의 인덱스입니다.

 

59~60라인은 에라스토테네스의 체 알고리즘을 응용한 부분입니다.

우선 위에서 구한 인덱스에 해당하는 배열 값을 0으로 변경해줍니다.

그 후 인덱스에 제곱수를 더해서 인덱스 값을 다시 계산하고 해당 인덱스의 배열 값을 0으로 변경해줍니다.

위에서 말한 for문의 증감 식이 의미하는 바는 제곱수의 배수에 대해서 모두 값을 변경해주는 것입니다.

값을 0으로 변경하는 이유는 "제곱ㄴㄴ수"를 판별하기 위해서 "제곱ㄴㄴ수"를 제외한 모든 값은 0으로 바꿔주는 것입니다.

 

65~69라인은 배열을 순회하면서 "제곱ㄴㄴ수"의 개수를 세는 코드입니다.

 

코드 자체는 전체적으로 길거나 어렵지 않지만, 백준 온라인 저지에서 골드 1 레벨에 해당하는 문제인 만큼 처음에 접근법을 생각해내기가 어렵습니다.

저도 에라스토테네스의 체까지는 생각을 했는데 가장 처음 제곱수로 나누어지는 수의 인덱스를 찾는 방법을 생각해내는데 오래 걸렸고 그 덕에 코드가 많이 지저분합니다 ㅠ

접근법을 알고 있으면 for문 대신에 while문을 써서 변수 몇 개를 인덱스로 지정해서 코드를 짜면 조금 더 깔끔하게 짤 수 있을 것 같습니다.

감사합니다.

---