풀이 핵심은 끝나는 시간을 기준으로 정렬하는 것이었다. 이후 반복문을 돌며 각 강의의 시작하는 시간과 마지막 끝난 시간을 비교하여 후자가 더 작을 때 마지막 끝난 시간을 업데이트해주며, 강의 수를 카운트 해주었다. #include #include #include using namespace std; int N; int main(int argc, char** argv) { cin >> N; vector vec(N); for(int i = 0; i > vec[i].second >> vec[i].first; } sort(vec.begin(), vec.end()); int cnt = 0; int lastEndTime = 0; for(int i=0;i=lastEndTime){ las..

풀이 분할정복을 활용한 문제였다. 재귀를 통해 제곱수를 구해주어야 하는데 문제 부분에서 0.1초당 P가 곱해지기 때문에 N에 10을 곱한 값을 인자로 넘겨주어야 한다. 이후 1승은 P를 리턴해주는 베이스를 만들고, 제곱수를 분할한다. 짝수승의 경우 반환받은 제곱수를 곱해주면 되지만, 홀수승의 경우에는 P를 곱해주어 값을 구해주고 반환해줘야 한다. #include using namespace std; long long K,P,N; long long f(long long cur){ if(cur==1) return P; long long result = f(cur/2); result = result * result % 1000000007; if(cur%2==1) result = result * P % 1000..

풀이 배열 내에서 연속으로 증가하는 개수의 최댓값을 구하는 문제였다. 먼저 dp 배열 내 모든 원소에 1을 저장시켜준 후 2중 for문을 통해 dp를 진행시켰다. 사용된 점화식은 다음과 같다. dp[i] = max(dp[i],dp[j]+1) i보다 작은 인덱스들에 한해서 현재 i레벨에서 저장된 값보다 작은 값이 있으면, 이전 레벨에서의 dp값에 1을 더하며 최댓값을 구하였다. #include #include using namespace std; int N,dp[3001]; int main(int argc, char** argv) { int ans=0; cin>>N; fill(dp,dp+N,1); vector v(N); for(int i=0;i>v[i]; } for(int i=0;i

풀이 매개변수를 이용한 이분탐색 알고리즘 문제였다. 처음에 문제의 조건에서 B의 크기에 간과하여 시간이 꽤 소요되었는데, cost를 계산 후 매개변수의 차이의 합을 저장하던 중 자료형의 크기를 훨씬 넘어버리는 케이스를 생각하지 못하였다. overflow가 발생하면 더이상 차이의 합을 저장하지 않고 bool 타입 변수를 true로 조정 후 break문을 사용하여 넘어가는게 핵심이었던 문제이다. #include #include #include #include using namespace std; long long N,B,ans; vector vec; int main(int argc, char** argv) { cin>>N>>B; vector vec(N); for(int i=0;i>vec[i]; } sort(..

풀이 정렬 알고리즘의 응용 문제였다. 구현의 핵심은 역순 정렬 후 중복되는 값을 처리하는 로직이었는데, 처음에 count 함수를 사용해서 중복처리 로직설계를 진행하였다가 시간초과가 발생하였다. 이후에 rank라는 포인터를 지정 후 이를 사용하여 중복되는 숫자에 대해 처리를 해주니 시간초과 문제가 해결되었다. #include #include #include using namespace std; int N; vector vec[4]; int order[4][100001]; int main(int argc, char** argv) { cin >> N; for (int i = 0; i > score; vec[..

풀이 연비의 중앙값을 이분탐색을 통해 구하여 경우의 수를 계산해주면 되는 간단한 문제였다. 우선 중앙값을 먼저 이분탐색을 통해 찾아준다. 이때 인덱스를 얻어야 하기 위해 lower_bound를 사용하며, 마지막에 첫번째 반복자를 빼줌으로써 인덱스를 얻는다. 이후 중앙값이 되는 가짓수를 계산하는 방법으로 중앙값 기준으로 (왼쪽 요소의 수 * 오른쪽 요소의 수)를 곱해주면 모든 경우의 수를 구할 수 있었다. #include #include #include using namespace std; int n,q; vector vec,m; int main(int argc, char** argv) { cin>>n>>q; vec.resize(n); m.resize(q); for(int i=0;i>vec[i]; } so..