쾌락없는 책임 (공부)/알고리즘 문제풀이
-
13975 백준 - 파일 합치기 3, C++, 우선순위 큐쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 18. 14:43
13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net #include #include using namespace std; int t; int main(){ scanf("%d", &t); while (t--){ long long ans = 0, input; int k; priority_queue pq; scanf("%d", &k); for(int i = 0; i < k; i++){ scanf("%lld", &input); pq.push(-input); } int count = 0; while(!pq.empty()..
-
1647 백준 - 도시 분할 계획, C++, 크루스칼 알고리즘쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 17. 18:23
1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net #include #include #include using namespace std; int n, m, ans; int parent[100001]; vector edge; int FindParent(int x){ if(x == parent[x]) return x; else return parent[x] = FindParent(parent[x]); } bool IsSameParent(int x, int y){ x = FindP..
-
11003 백준 최솟값 찾기 - C++, 덱쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 16. 22:59
11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net #include #include using namespace std; int numbers[5000001]; int n, l; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> l; for(int i = 0; i > numbers[i]; deque list; for(int i = 0; i < n; i++){ if(!..
-
1823 백준 수확 - C++, DP쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 9. 16. 18:18
1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net #include #include using namespace std; int n, res; int rice[2001]; int dp[2001][2001]; int DP(int left, int right, int count){ if(left > right) return 0; if(dp[left][right]) return dp[left][right]; return dp[left][right] = max(DP(left+1, right, count+1) + rice[left] * count, DP(l..
-
백준 12738 가장 긴 증가하는 부분수열 3 - C++, LIS쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 8. 23. 21:32
12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net #include #include #include using namespace std; int n, input; int main(){ scanf("%d", &n); vector num; for(int i = 0; i < n; i++){ scanf("%d", &input); if(num.empty() || num.back() < input) num.push_back(input); else { auto temp = lower_bound(num.begin(), num.e..
-
백준 20040 사이클 게임 - C++, Disjoint Set쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 8. 19. 13:19
20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #include using namespace std; int parent[500001]; int n, m; int FindParent(int x){ if(x == parent[x]) return x; else return parent[x] = FindParent(parent[x]); } void Merge(int x, int y){ x = FindParent(x); y = FindParent(y); if(x == y) return; parent[x] = y;..
-
백준 1563 개근상 - C++, DP, 재귀쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 8. 11. 19:39
1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net #include #include #define MOD 1000000 using namespace std; int n; int arr[1001][1001][2][3]; // 결석 연속 3번 불가 지각 2번 불가 (지각은 연속 아님) int school(int day, int attend, int delay, int absent){ if(delay == 2 || absent == 3) return 0; if(day == n) return 1; if(arr[day][attend]..