백준 11332번 시간초과 :: 마이구미

이 글은 백준 알고리즘 문제 11332번 "시간 초과" 를 풀이한다.

정답 비율이 낮지만, 어려운 알고리즘을 요구하진 않는다.

제목처럼 항상 시간초과를 고려했다면, 쉽게 문제를 해결할 수 있다.

문제 링크 - https://www.acmicpc.net/problem/11332

유빈이는 코딩을 하다가 시간 초과가 났다. 그래서 시간 복잡도를 계산하기로 했다.

채점 시스템은 1초에 100000000(108)가지 동작을 할 수 있다.

여러분들은 유빈이를 도와 시간초과가 나는지 확인하는 프로그램을 작성하라.

입력의 첫 번째 줄에는 테스트 케이스들의 수 C가 주어진다.

그 다음 C개의 줄에는 시간 복잡도를 나타내는 문자열 S, 각 테스트 케이스마다 입력의 최대 범위 N, 테스트 케이스의 수를 나타내는 T랑 제한시간(초 단위) 를 나타내는 L이 주어진다. (1 <= C <= 100, 1 <= N <= 1000000, 1 <= T, L <= 10, N, T, L은 정수)

시간 복잡도는 다음과 같은 5개 중 하나로 주어진다.

• O (N)
• O (N^2)
• O (N^3)
• O (2^N)
• O (N!)

문제는 5개의 시간 복잡도를 고려하면 된다.

알고리즘 문제에 대해 시간을 고려할 때, 대부분 반복문의 횟수로 판단한다.

예를 들어, 반복문이 1억번 실행될 경우, 1초가 걸린다고 가정한다.

다음과 같이 시간초과 여부를 확인할 수 있다.

if 시간복잡도 * C(테스트케이스 수) <= L * 100000000 시간초과 X
else 시간초과 o

다음 예제를 통해 확인해보자.

N = 20, C = 10, L = 1
O(N) => 20 * 10 = 200 <= 100000000 true
O(N^2) => 20^2 = 400 * 10 = 4000 <= 100000000 true
O(N^3) => 20^3 = 8000 * 10 = 80000 <= 100000000 true
O(2^N) => 2^20 = 1048576 * 10 = 10485760 <= 100000000 true
O(N!) => 2432902008176640000 = 24329020081766400000 <= 100000000 false

보다시피 일반적인 int 범위로는 표현할 수 없다.

그로인해, 정답 비율이 낮은 이유는 범위를 고려하지 않았기 때문일 것이다.

하지만 범위를 고려했더라도, 시간복잡도 O(N!) 의 경우에 문제가 발생한다.

시간복잡도 O(N!) 의 경우 N이 20인 경우에도 엄청난 수로 표현되는 것을 볼 수 있다.

웬만한 타입으로는 모든 범위를 표현하지 못한다.

그렇기에, 해결책으로는 O(N!) 계산 시에는 모든 계산을 하지 않고, 그 도중에 중단해야하는 대안을 해주면 된다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/biginteger/11332.java

private void solve() {
    int c = sc.nextInt();
    StringBuilder sb = new StringBuilder();
 
    while(c-- > 0) {
        String s = sc.next();
        String n = sc.next();
        BigInteger t = new BigInteger(sc.next());
        BigInteger l = new BigInteger(String.valueOf(sc.nextInt() * 100000000));
        BigInteger bi = new BigInteger(n);;
 
        if (s.equals("O(N)")) {
            if (bi.multiply(t).compareTo(l) == 1) {
                sb.append("TLE!\n");
            } else {
                sb.append("May Pass.\n");
            }
        } else if (s.equals("O(N^2)")) {
            if (bi.pow(2).multiply(t).compareTo(l) == 1) {
                sb.append("TLE!\n");
            } else {
                sb.append("May Pass.\n");
            } 
        } else if (s.equals("O(N^3)")) {
            if (bi.pow(3).multiply(t).compareTo(l) == 1) {
                sb.append("TLE!\n");
            } else {
                sb.append("May Pass.\n");
            } 
        } else if (s.equals("O(2^N)")) {
            bi = new BigInteger("2");
            if (bi.pow(Integer.valueOf(n)).multiply(t).compareTo(l) == 1) {
                sb.append("TLE!\n");
            } else {
                sb.append("May Pass.\n");
            } 
        } else {
            int N = Integer.valueOf(n);
            while(N-- > 1) {
                bi = bi.multiply(new BigInteger(String.valueOf(N)));
                if (bi.compareTo(l) == 1) {
                    break;
                }
            }
            if (bi.multiply(t).compareTo(l) == 1) {
                sb.append("TLE!\n");
            } else {
                sb.append("May Pass.\n");
            } 
        }
    }
    System.out.println(sb.toString());
}