[BOJ/Silver 3] 백준 11332 시간초과(C++)

문제 링크

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

11332번: 시간초과

 

문제

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

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

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

입력

입력의 첫 번째 줄에는 테스트 케이스들의 수 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!)

출력

각 테스트 케이스들에 대하여 시간 초과가 나면 "TLE!", 시간 초과가 나지 않으면 "May Pass." 를 출력한다.

예제 입력 1

5
O(N) 1000 10 10
O(2^N) 1000 10 10
O(N!) 2 10 10
O(N^3) 1000 1 10
O(N^3) 1001 1 10

예제 출력 1

May Pass.
TLE!
May Pass.
May Pass.
TLE!

알고리즘 분류

• 많은 조건 분기

풀이

시간복잡도가 O(N)일 때 : N*T가 L*1억 이하면 통과이며, 초과면 TLE이다.

시간복잡도가 O(N^2)일 때 : N이 31623이 넘어간다면 테스트 케이스가 1일 때 처리해야 할 동작이 10억개가 넘어간다. 따라서 무조건 TLE가 발생할 것이다. N이 31623 미만이라면 (N^2)*T가 L*1억 이하면 통과이며, 초과면 TLE이다.

시간복잡도가 O(N^3)일 때 : N이 1001이 넘어간다면 테스트 케이스가 1일 때 처리해야 할 동작이 10억개가 넘어간다. 따라서 무조건 TLE가 발생할 것이다. N이 1001 미만이라면 (N^3)*T가 L*1억 이하면 통과이며, 초과면 TLE이다.

시간복잡도가 O(2^N)일 때 : N이 30이 넘어간다면 테스트 케이스가 1일 때 처리해야 할 동작이 10억개가 넘어간다. 따라서 무조건 TLE가 발생할 것이다. N이 30 미만이라면 (2^N)*T가 L*1억 이하면 통과이며, 초과면 TLE이다.

시간복잡도가 O(N!)일 때 : N이 13이 넘어간다면 테스트 케이스가 1일 때 처리해야 할 동작이 10억개가 넘어간다. 따라서 무조건 TLE가 발생할 것이다. N이 13 미만이라면 (N!)*T가 L*1억 이하면 통과이며, 초과면 TLE이다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100000000
#define LL long long
#define INF 1e9

using namespace std;
int C;
string S;
LL N, T, L;

void Input() {
	cin >> C;
}

void Settings() {
	if (S == "O(N)") {
		LL Sum = N * T;
		if (Sum <= (L * MAX)) {
			cout << "May Pass.\n";
		}
		else {
			cout << "TLE!\n";
		}
	}
	else if (S == "O(N^2)") {
		if (N >= 31623) {
			cout << "TLE!\n";
		}
		else {
			LL Sum = (N * N * T);
			if (Sum <= (L * MAX)) {
				cout << "May Pass.\n";
			}
			else {
				cout << "TLE!\n";
			}
		}
	}
	else if (S == "O(N^3)") {
		if (N >= 1001) {
			cout << "TLE!\n";
		}
		else {
			LL Sum = (N * N * N * T);
			if (Sum <= (L * MAX)) {
				cout << "May Pass.\n";
			}
			else {
				cout << "TLE!\n";
			}
		}
	}
	else if (S == "O(2^N)") {
		if (N >= 30) {
			cout << "TLE!\n";
		}
		else {
			LL Sum = (LL)pow(2, N) * T;
			if (Sum <= (L * MAX)) {
				cout << "May Pass.\n";
			}
			else {
				cout << "TLE!\n";
			}
		}
	}
	else if (S == "O(N!)") {
		if (N >= 13) {
			cout << "TLE!\n";
		}
		else {
			LL Sum = T;
			for (LL i = 1; i <= N; i++) {
				Sum *= i;
			}
			if (Sum <= (L * MAX)) {
				cout << "May Pass.\n";
			}
			else {
				cout << "TLE!\n";
			}
		}
	}
}

void Find_Answer() {
	while (C--) {
		cin >> S >> N >> T >> L;
		Settings();
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}