[ 백준 ] 11332 / 시간초과
# Appreciation
/*
* Problem :: 11332 / 시간초과
*
* Kind :: Simulation
*
* Insight
* - 시간복잡도 <= L*10^8 이어야 시간초과가 나지 않는다
* + O(N) -> N*T <= L*10^8
* O(N^2) -> N*N*T <= L*10^8
* O(N^3) -> N*N*N*T <= L*10^8
* O(2^N) -> 2^N*T <= L*10^8
* O(N!) -> N!*T <= L*10^8
* 각 경우마다 시간복잡도를 계산해서 제한시간과 비교해주면 된다
* # 역시나 Overflow 가 문제인데...
* 그래서 그냥 double 자료형을 사용했다
* max(N)=10^6, max(T,L)=10 인데
* 12자리 이상의 정밀도를 보존하는 double 자료형이라면 괜찮을 것 같았다
* -> 그래서 N, T, L 모두 double 자료형으로 값을 받았다
*
* Point
* - 2^N 이나 N! 은 N, N^2, N^3 과 달리
* N 이 조금만 커져도 상상을 초월하는 큰 수가 된다
* 그래서 계산중간에 L*10^8 을 넘으면 불가능하다고 판단했었다
* + 곰곰이 생각해보니 log2 를 활용하면 좀더 간단히 판별할 수 있다
* 2^N*T <= L*10*8
* 2^N <= L*10*8/T
* N <= log2(L*10*8/T)
* # <cmath> 의 log2 를 사용해주자
* + 마찬가지로 팩토리얼도 직접 계산할 필요없이
* 팩토리얼로 계산한 로그를 얻으면(정수부분만) 좀더 간단히 판별할 수 있다
* # 함수이름을 logf 로 하고 싶었는데 <cmath> 에 이미 존재해서 충돌이 계속 일어났다
* 그래서 log_f 로 선언하였따
* -> 불편...
*/
# Code
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cmath>
using namespace std;
#define endl '\n'
// Set up : Global Variables
/* None */
// Set up : Functions Declaration
double log_f(double n);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int C; cin >> C;
while (C--) {
string S; double N, T, L;
cin >> S >> N >> T >> L;
// Process
L *= 100'000'000;
L /= T; /* 제한시간 */
bool isPossible = true;
if (S == "O(N)" && N > L) { isPossible = false; }
if (S == "O(N^2)" && N*N > L) { isPossible = false; }
if (S == "O(N^3)" && N*N*N > L) { isPossible = false; }
if (S == "O(2^N)" && N > log2(L)) { isPossible = false; }
if (S == "O(N!)" && N > log_f(L)) { isPossible = false; }
// Control : Output
cout << ((isPossible) ? "May Pass." : "TLE!") << endl;
}
}
// Helper Functions
double log_f(double n)
/* 정수부분의 팩토리얼 로그를 구하는 함수 */
{
int i = 1; double v = 1;
while ((v *= ++i) <= n);
return i-1;
}
Author And Source
이 문제에 관하여([ 백준 ] 11332 / 시간초과), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-11332-시간초과
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 11332 / 시간초과
*
* Kind :: Simulation
*
* Insight
* - 시간복잡도 <= L*10^8 이어야 시간초과가 나지 않는다
* + O(N) -> N*T <= L*10^8
* O(N^2) -> N*N*T <= L*10^8
* O(N^3) -> N*N*N*T <= L*10^8
* O(2^N) -> 2^N*T <= L*10^8
* O(N!) -> N!*T <= L*10^8
* 각 경우마다 시간복잡도를 계산해서 제한시간과 비교해주면 된다
* # 역시나 Overflow 가 문제인데...
* 그래서 그냥 double 자료형을 사용했다
* max(N)=10^6, max(T,L)=10 인데
* 12자리 이상의 정밀도를 보존하는 double 자료형이라면 괜찮을 것 같았다
* -> 그래서 N, T, L 모두 double 자료형으로 값을 받았다
*
* Point
* - 2^N 이나 N! 은 N, N^2, N^3 과 달리
* N 이 조금만 커져도 상상을 초월하는 큰 수가 된다
* 그래서 계산중간에 L*10^8 을 넘으면 불가능하다고 판단했었다
* + 곰곰이 생각해보니 log2 를 활용하면 좀더 간단히 판별할 수 있다
* 2^N*T <= L*10*8
* 2^N <= L*10*8/T
* N <= log2(L*10*8/T)
* # <cmath> 의 log2 를 사용해주자
* + 마찬가지로 팩토리얼도 직접 계산할 필요없이
* 팩토리얼로 계산한 로그를 얻으면(정수부분만) 좀더 간단히 판별할 수 있다
* # 함수이름을 logf 로 하고 싶었는데 <cmath> 에 이미 존재해서 충돌이 계속 일어났다
* 그래서 log_f 로 선언하였따
* -> 불편...
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <cmath>
using namespace std;
#define endl '\n'
// Set up : Global Variables
/* None */
// Set up : Functions Declaration
double log_f(double n);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
int C; cin >> C;
while (C--) {
string S; double N, T, L;
cin >> S >> N >> T >> L;
// Process
L *= 100'000'000;
L /= T; /* 제한시간 */
bool isPossible = true;
if (S == "O(N)" && N > L) { isPossible = false; }
if (S == "O(N^2)" && N*N > L) { isPossible = false; }
if (S == "O(N^3)" && N*N*N > L) { isPossible = false; }
if (S == "O(2^N)" && N > log2(L)) { isPossible = false; }
if (S == "O(N!)" && N > log_f(L)) { isPossible = false; }
// Control : Output
cout << ((isPossible) ? "May Pass." : "TLE!") << endl;
}
}
// Helper Functions
double log_f(double n)
/* 정수부분의 팩토리얼 로그를 구하는 함수 */
{
int i = 1; double v = 1;
while ((v *= ++i) <= n);
return i-1;
}
Author And Source
이 문제에 관하여([ 백준 ] 11332 / 시간초과), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-11332-시간초과저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)