본문 바로가기

전체 글

 (74)
[BOJ 2042] 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Tag : segment tree 풀이 두가지 풀이가 있다. 1. 세그먼트 트리 : \(O(QlogN)\) 2. 누적합 + 변화량만 따로 저장 : \(O(N + Q^2)\) 구간 합 구하기 2에는 simd 펜윅을 박은 분이 1등이던데 이 문제에는 그런 제출이 없어서 다행.. 코드 #pragma GCC optimize ("O3") #prag..
Codeforces Round #766 (Div. 2) https://codeforces.com/contest/1627 Dashboard - Codeforces Round #766 (Div. 2) - Codeforces codeforces.com b치고 좀 어려운 놈이 있었고, c에 그래프 + 구성적, d는 쉬운 정수론... 바람직한 셋이었다. 이번 셋을 잘풀어서 1854 퍼포먼스를 뽑았는데 기분이 좋다. A. Not Shading Tag : 무지성 풀이 (r, c)가 B라면 0, 같은 행 또는 열에 B가 존재한다면 1 아니면 2이다. 전체에 B가 하나도 없다면 -1을 출력하면 된다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; void so..
Codeforces Round #716 (Div. 2) https://codeforces.com/contest/1514 Dashboard - Codeforces Round #716 (Div. 2) - Codeforces codeforces.com 오랜만에 버춸 돌았다. 퍼포먼스가 1980쯤 나와서 기분이 좋다. A. perfectly Implerfect Array Tag : math 풀이 길이가 3이상인 답안에서 제곱수가 되는 것들을 모두 제외해서 그 길이를 1 또는 2로 만들 수 있다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); //freopen("i..
FastIO 템플릿 #include #include #include template struct FASTIO { char *p,O[2000000],*d; void set() { struct stat st;fstat(0,&st);d=O; p=(char*)mmap(0,st.st_size,1,1,0,0); } ~FASTIO() { write(1,O,d-O); } inline T get() { T x=0;bool e;p+=e=*p=='-'; for(;*p==10 or *p==32;p++); for(char c=*p++;c&16;x=10*x+(c&15),c=*p++); return e?-x:x; } inline void put(T x) { if(d-O+100>2000000) write(1,O,d-O), d=O; if(x
[BOJ 8903] 장비 https://www.acmicpc.net/problem/8903 8903번: 장비 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다 www.acmicpc.net Tag : case work 문제요약 장비마다 5개의 능력치가 있는데 장비를 여러개 골랐을 때 각각의 능력치는 고른 장비들에서 최대 하나로만 결정된다. 고를 수 있는 장비의 개수가 주어졌을 때 능력치 합의 최대를 구하라. 풀이 5개 이상 고를 수 있다면 각각의 능력치가 최대인 것을 하나씩 골라오면 된다. 그게 아니라면 \(O(2^{10} \times N)\) 비트마스킹..
[BOJ 16474] 이상한 전깃줄 https://www.acmicpc.net/problem/16474 16474번: 이상한 전깃줄 엘리트 도로설계사 현정이는 도로 위 전봇대 사이에 연결된 전깃줄을 관리하는 일을 한다. 도로 양 옆에는 각 고유번호를 갖고 있는 전봇대가 여러 개 있다. 마을에 최대한 많은 양의 전력을 보 www.acmicpc.net Tag : lis 문제요약 전깃줄의 연결 상태가 입력으로 들어오는데 이 때 전깃줄을 최소한으로 끊어서 전깃줄이 교차하지 않는 상태를 만드는 것이 목표이다. 전깃줄을 끊는 최소 횟수를 구하라. 풀이 입력을 조금만 손보면 \(O(N^2)\) lis 문제가 된다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll..
[BOJ 23578] 비 오는 날 https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net Tag : greedy 문제요약 스패닝 트리를 만드는데 \( \sum{ (degree_i)^2 * a_i } \)를 최소화해라 풀이 처음에 이상한 전략을 많이 생각했다. 일단 \(a_i\)에 비례하게 분배해놓고 이득이 되는 쪽으로 옮긴다던지.... 그런데 이걸 잘 정리하다보니까 그냥 처음부터 최소화되는 쪽으로 이어가는게 낫다는 결론이 나왔다. 일단 모든 정점에서 \( degree_i \)가 1 이상이라..
[BOJ 10523] 직선 찾기 https://www.acmicpc.net/problem/10523 10523번: 직선 찾기 입력 예제 1에서 (0, 0) / (3, 3) / (10, 10)을 지나는 직선을 찾을 수 있다. 2.75개 이상의 점을 지났으니 그러한 직선이 있다고 볼 수 있다. www.acmicpc.net Tag : random 문제요약 N개의 점이 이차원 좌표평면 위에 있을 때 이 중 p퍼센트 이상의 점을 지나는 직선이 있는지 판별하라. 풀이 답이 possible이면서 시간복잡도 상으로 최악일 경우를 생각해보자. k = \( \lfloor \frac{n \times p}{100} \rfloor \)일 때 k개의 점을 지나는 직선이 딱 1개 있는 경우일 것이다. 서로 다른 두 점을 아무렇게나 한번 골라서 이 두 점을 지나는..

티스토리툴바