• 백준 11332번 시간초과 :: 마이구미
    알고리즘 풀이/수학 2018. 1. 28. 16:40
    반응형

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    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());
    }
    cs


    반응형

    댓글

Designed by Tistory.