www.acmicpc.net/problem/1100011000번: 강의실 배정첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)www.acmicpc.net강의실 배정 문제다. 어떻게 하면 최대한 적은 강의실을 사용해서 모든 강의를 할 것인지를 찾아내면 된다.처음에는 회의실 배정 문제랑 비슷한 문제인 것 같아서 강의 종료 시점을 기준으로 정렬해서 제출했는데 틀렸다.찾아보니 priority_queue를 사용해서 시작시간을 기준으로 해결해야 한다.큐는 최소 힙으로 선언해주고 큐에는 종료시간만 삽입한다. 대략적인 접근방법은 이렇다.벡터에 pair로 시작시간, 종료시간을 입력받는다시작시간을 기준으로 정렬하고 priority_..

www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 49가지 수 중에서 6개를 뽑아 출력하는 문제다. 백트래킹을 이용한 조합 문제였다. n과 m을 푼 게 도움이 됐다. #include #include #include using namespace std; void dfs(int cnt, int idx, vector& ar, vector& tmp, vector vis) { if (cnt == 6) { for (int i = 0; i < cnt; i++) ..

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 두 포인터를 활용한 재미있는 문제였다. n을 입력받아서 소수 판정을 해주고 prime 배열에 넣어주고 두 포인터를 쓰면 된다. #include #include using namespace std; const int MX = 4000001; vector sieve; vector prime; int s, e, sum, cnt; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i = n) sum -= prime[s++..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 슬라이딩 윈도를 사용해서 공간 복잡도를 O(1)로 만들고 풀어야 하는 문제. 라이님의 블로그를 참고해서 풀었다. DP식 짜는 것은 매우 쉽지만 필요 메모리가 무려 4MB이다... DP 식을 잘 보면 cin >> TMX[j]; TMN[j] = TMX[j]; TMX[j] += max(MX[1], (j == 1) ? max(MX[0], MX[2]) : MX[j]); TMN[j] += min(MN[1], (j == 1) ? min(..

www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 � www.acmicpc.net 각각 i부터 j까지의 부분합 중 k인 수가 몇 개인지 세는 문제이다. 일단 prefix sum을 통해서 배열을 채웠는데 for (int i = 1; i > x; d[i] += d[i - 1] + x; } 이 후가 문제이다. 여기서 각각의 원소에 대해서 \(O(N^2)\) 으로 짜면 시간 초과가 난다. 따라서 i 부터 j 사이의 부분합의 개수..

www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 정수형 배열을 입력받고 구간의 값이 팰린드롬인지 판단하는 문제다. 처음에는 문자열로 접근해서 reverse를 사용했지만 2000번에 대해서 1백만 번씩 뒤집히니 시간 초과. 결국 dp로 풀었다. #include #include using namespace std; int f(vector& d, vector& ar, int s, int e) { if (s >= e) return 1; if (d[s][e] != -1) return d[s][e]; if ..