-
백준 11332번 시간초과 :: 마이구미알고리즘 풀이/수학 2018. 1. 28. 16:40반응형
이 글은 백준 알고리즘 문제 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
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253private 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 반응형'알고리즘 풀이 > 수학' 카테고리의 다른 글
백준 2505번 두 번 뒤집기 :: 마이구미 (1) 2018.02.05 백준 2564번 경비원 :: 마이구미 (0) 2018.01.29 백준 2477번 참외밭 :: 마이구미 (0) 2017.12.28 백준 10800번 컬러볼 :: 마이구미 (2) 2017.12.21 백준 2980번 도로와 신호등 :: 마이구미 (0) 2017.12.17