[자바] 백준 2986 - 파스칼 (java)

 문제 : boj2986

---

 

필요 알고리즘 개념

•  소수 판정
  • 소수 판정 시 소수인지 알고 싶은 값 N에 대해 sqrt(N) 까지만 살펴보면 된다는 점을 알아야 풀 수 있다.
  • 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 글에서 해당 개념을 익힐 수 있다.
• 수학, 정수론
  
  • 기본적인 수학 지식이 있어야 풀 수 있다. 정확힌 나머지 연산에 대한 개념과 소수(prime number)가 무엇인지, 약수가 무엇인지 정도만 알면 된다.
  • 나머지 연산 : 코드에서는 일반적으로 '%'로 표현된다. A%B는 A를 B로 나누고 남은 나머지를 뜻한다. A%B==0 이라면 B가 A의 약수임을 뜻한다.
  • 소수(prime number) : 2이상의 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 예를들어 2,3,5,7,11이 있다.
  • 약수(divisor) : 어떤 수를 나누어떨어지게 하는 수이다. 즉, A%B == 0이라면 B는 A의 약수이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 문제에서 제시된 수도코드가 뭘 의미하는지 코드적으로 이해하지 못할 수 있으니 자바코드로 확인해보자.

private void solution() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int counter = 0;
    for (int i = N-1; i >= 1; i--) {
        counter = counter + 1;
        if (N % i == 0)
            break;
    }
    System.out.println(counter);
}

 

---

 

  그냥 문제에서 제시된 대로 짠 코드이다. 이 경우 당연히 이대로 제출하게되면 O(N)의 시간복잡도를 가지고, N은 최대 10^9이므로 시간초과로 통과할 수 없다. 따라서 위 코드가 무엇을 의미하는지 파악해서 더 작은 시간복잡도를 가지도록 해야한다.

 

  위 코드를 말로 설명해보면 "N-1부터 1씩 감소하면서 N의 가장 큰 약수를 구하려면 몇 번 감소시켜야 하냐?" 이다. 이걸 O(N)으로 짠게 위 코드이다. 그럼 좀 더 짧은 시간 내에 N의 가장 큰 약수를 알 수 있고 그걸 X라고 해보자. 그럼 답은 N-X가 될 것임을 알 수 있다(N-1부터 X까지 1씩 감소한 횟수가 문제에서 제시된 counter 이므로). 추가로 만약 N이 소수일 경우 1까지 내려가야 답이 찾아질 것이므로 무조건 'N-1'이 답이 된다.

 

  그럼 이제 X(N의 가장 큰 약수)를 찾아보자. 한가지 아이디어는, 더 작은 수로 나눌수록 더 큰 약수를 발견할 수 있다는 점이다. 예를들어 1,000,000,000의 가장 큰 약수는 단순히 2를 나눈 값인 500,000,000이 X가 될 것이다. 999,999,999의 경우엔 2로 나눈 경우엔 나누어떨어지지 않고, 3으로 나누었을 때의 333,333,333이 X가 될 것이다. 즉, 2부터 1씩 증가시키면서 해당 수로 나누어 떨어진다면, N-X가 답이 되므로 N-(N/i)가 답이 될 것이다(i는 2부터 증가하는 값).

 

  즉 대강 아래와 같이 짜면 될 것 같다.

for (int i = 2; i <= N/2; i++) {
    if (N%i == 0) {
        System.out.println(N-N/i);
        return;
    }
}

하지만 위의 경우에도 역시 N이 소수일 경우 끝까지 모두 살펴봐야 한다. 따라서 O(N)이므로 통과할 수 없다.

여기서 팁은 사실 sqrt(N) 까지만 살펴보면 된다는 점이다. N의 가장 큰 약수는 무조건 N/sqrt(N) 이내에서 발생할 수밖에 없다. 해당 내용은 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유에서 이해해보자. 아무튼 그럼 바꿔보면 아래와 같다. 이 경우 O(sqrt(N))이 되므로 문제없이 통과 가능하다.

int sqrtN = (int) Math.sqrt(N);
for (int i = 2; i <= sqrtN; i++) {
    if (N%i == 0) {
        System.out.println(N-N/i);
        return;
    }
}

 

---

 

  추가로 좀 더 줄여보자. 어차피 2로 나누어 떨어지지 않았다면, 이후에 짝수로는 나누어 떨어질 수 없다. 따라서 2만 체크해주고 그 이후로는 3 이상의 홀수로만 나누어 떨어지는지 체크해줘도 된다. 이하 첨부한 코드는 그렇게 짠 코드이니 뭐가 바꼈는지 확인해보자. 참고로 O(sqrt(N)) 만으로도 충분히 엄청 빠르게 통과 가능한 로직이라 크게 시간차이는 없으나, 약간 차이가 나긴 한다(76ms vs 84ms). 이론상으론(?) 2배 빠르긴 하다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int sqrtN = (int) Math.sqrt(N);
        if (N%2 == 0) {
            System.out.println(N/2);
            return;
        }
        for (int i = 3; i <= sqrtN; i+=2) {
            if (N%i == 0) {
                System.out.println(N-N/i);
                return;
            }
        }
        System.out.println(N-1);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}