본문 바로가기

BOJ78

BOJ 11000 강의실 배정 www.acmicpc.net/problem/1100011000번: 강의실 배정첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)www.acmicpc.net강의실 배정 문제다. 어떻게 하면 최대한 적은 강의실을 사용해서 모든 강의를 할 것인지를 찾아내면 된다.처음에는 회의실 배정 문제랑 비슷한 문제인 것 같아서 강의 종료 시점을 기준으로 정렬해서 제출했는데 틀렸다.찾아보니 priority_queue를 사용해서 시작시간을 기준으로 해결해야 한다.큐는 최소 힙으로 선언해주고 큐에는 종료시간만 삽입한다. 대략적인 접근방법은 이렇다.벡터에 pair로 시작시간, 종료시간을 입력받는다시작시간을 기준으로 정렬하고 priority_.. 2020. 10. 2.
BOJ 2437 저울 www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 추가 주어진다면 오름차순 정렬을 해주고 현재까지의 누적합 + 1 이 현재의 추보다 더 크다면 그 누적합 + 1 이 구할 수 없는 최솟값이 된다. 그 이하의 수들은 현재까지의 추들로 모두 조합할 수 있다. #include #include using namespace std; int ar[1001]; int main() { int n; cin >> n; for (int i = 0; i > ar[i.. 2020. 10. 2.
BOJ 6603 로또 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++) .. 2020. 9. 29.
BOJ 1644 소수의 연속합 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++.. 2020. 9. 23.
BOJ 2096 내려가기 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(.. 2020. 9. 23.
BOJ 2015 수들의 합 4 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 사이의 부분합의 개수.. 2020. 9. 23.

티스토리툴바