[BOJ 5615] 아파트 임대 (Java)

BOJ 5615 아파트 임대

난이도 : 플래 1

https://www.acmicpc.net/problem/5615

5615번: 아파트 임대

 

전략

주어진 면적 S에 대해서 S = 2xy + x + y (x, y는 양의 정수)의 해를 가지는가를 판별해야 한다.

(x + 1)(y + 1) - 1 = xy + x + y이므로 이 형태를 변형할 수 있을 것 같다.

(2x + 1)(2y + 1) - 1 = 4xy + 2x + 2y = 2S이다.

2S + 1 = (2x + 1)(2y + 1)

2S + 1은 홀수이므로 소수가 아니라면 두 홀수의 곱으로 나타낼 수 있다.

따라서 2S + 1이 소수인지 판별하는 문제로 변형할 수 있다.

 

S ≤ 2^31-1로 일반적인 sqrt 방법으로는 시간내에 판별할 수 없다.

따라서 정보보호이론 강의에서 배운 Miller-Rabin test로 판별하고자 한다.

이는 Fermat test와 Square Root test가 혼합된 방식이다. 이론적인 부분은 따로 정리하고자 한다.

 

밀러 라빈은 무작위로 liar가 선택될 확률이 1/4 이하이므로

10번을 기준으로 판별하도록 하였다.

 

맞왜틀?

1. long 범위 벗어남 -> BigInteger 사용

2. a^m mod n 과정에서 비효율 발생 -> O(logm)에 계산가능한 fastSquare 구현

3. 강의에서 배운 것처럼 랜덤하게 a 선택 -> 알려진 base 리스트를 이용하여 구현

4. 시간제한이 매우 타이트해서 직접 구현한 fastSquare 메소드도 시간초과 -> BigInteger 클래스의 modPow 메소드 이용

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

    static final long[] base = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int cnt = 0;
        for (int i=0; i<N; i++) {
            long s = Long.parseLong(br.readLine());
            long n = 2 * s + 1;

            if (n <= 4) {
                cnt += 1;
                continue;
            }
            boolean isPrime = true;
            for (int t=0; t<base.length; t++) {
                if (base[t] >= n)
                    break;

                if (!isPrime(n, base[t])) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                cnt += 1;
            }
        }

        System.out.println(cnt);
    }

    static boolean isPrime(long n, long a) {
        long m = n - 1;
        int k = 0;
        while (m % 2 == 0) {
            m = m >> 1;
            k += 1;
        }
//        BigInteger t = fastSquare(a, m, n);
        BigInteger t = BigInteger.valueOf(a).modPow(BigInteger.valueOf(m), BigInteger.valueOf(n));

        if (t.compareTo(BigInteger.ONE) == 0 || t.compareTo(BigInteger.valueOf(n - 1)) == 0)
            return true;

        BigInteger nBig = BigInteger.valueOf(n);
        for (int i = 1; i <= k - 1; i++) {
            t = t.multiply(t).mod(nBig);
            if (t.compareTo(BigInteger.ONE) == 0)
                return false;
            if (t.compareTo(BigInteger.valueOf(n - 1)) == 0)
                return true;
        }
        return false;
    }

    static BigInteger fastSquare(long a, long x, long n) {
        BigInteger y = BigInteger.ONE;
        BigInteger aBig = BigInteger.valueOf(a);
        BigInteger nBig = BigInteger.valueOf(n);

        while (x > 0) {
            if (x % 2 == 1)
                y = y.multiply(aBig).mod(nBig);
            aBig = aBig.multiply(aBig).mod(nBig);
            x = x >> 1;
        }
        return y;
    }
}

PS라서 간단하게 구현했지만, 효율적인 계산을 위해서는 작은 수에서는 알려진 소수로 나눠보는 방법을 사용하고

큰 수에 대해서는 적절한 a를 찾아서 밀러 라빈 테스트를 진행해야 한다.

처음에는 또한 [2, n-2] 범위에서 a를 적절하게 선택했지만, 매번 random을 구하는 것이 시간이 걸려서 알려진 base 배열을 두고 사용했다.

그리고 맞왜틀 부분에서 말한 것처럼 fastSquare 메소드를 만들긴 했지만.. BigInteger 클래스에 정의된 메소드가 더 빨랐다. 비트연산으로 구현되어서 그런 것 같다.

 

참고로 자바 BigInteger 클래스의 isProbablePrime() 메소드를 사용할 수도 있다.

 

깨달은 점

공부할 땐 괜찮았는데 ..  너무 오래걸렸다 울뻔했다.

여태까지 푼 문제 중에 가장 많은 시도를 했다