본문 바로가기

백준

 (223)
백준 2263 - 사탕상자 https://www.acmicpc.net/problem/2243 특정 맛을 가진 사탕의 개수를 변경하거나 k번째로 맛있는 사탕을 꺼내야 하는 질의를 최대 10만개 수행해야 한다. 세그먼트 트리를 통해 각 맛의 정도에 해당하는 사탕의 개수를 세그먼트 트리로 관리하면서 k번째로 맛있는 사탕(이하 k번째 사탕)을 추적하는 질의를 작성하면 된다. 맛의 정도를 index로 하여 배열을 구성하면 update는 구간합 용도로 구현한 세그먼트 트리의 그것과 동일하게 작성이 가능하다. k번째 사탕을 추적하는 질의는 현재 노드에서 왼쪽 구간의 사탕 개수와 오른쪽 구간의 사탕 개수를 비교한다. 만약 k보다 왼쪽 구간의 개수 이상이면 왼쪽 노드, 그렇지 않으면 오른쪽 노드로 가지치기 하여 로그 스케일로 줄여나가 원하는 사탕..
백준 13172 - Σ https://www.acmicpc.net/problem/13172 문제 요약 $N_{i}, \: S_{i}$가 M개 주어지는데 이들을 $a \times (b^{-1} \mod p)$ (p는 소수)의 형태로 바꾸고 그 합의 모듈러를 구하라. 풀이 문제에서 페르마의 소정리를 사용하라고 했으므로 페르마의 소정리를 통해 $N_{i} \mod p$를 구한 뒤 $S_{i}$를 곱하면 된다. 문제의 이름처럼 기대값들을 모두 더하는 것을 잊지 말자. 전체 코드 더보기 #include using namespace std; using ll = long long; #define mod 1000000007 int m; ll pomod(ll val, int b) { if (b == 1) return val % mod; if ..
백준 16928 - 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 다른 노드로 건너뛸 수 있는 간선이 주어진다는 것과 주사위의 점만큼 움직인다는 점을 기억하며 BFS를 수행하면 된다. 전체 코드 더보기 #include using namespace std; using pii = pair; int n, m; unordered_map warp; bool visited[101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i > go >> to; warp[go] = to; } queue q; q.push({1, 0}); visited[1] = ..
백준 12837 - 가계부 (Hard) https://www.acmicpc.net/problem/12837 가계부에 내용이 계속 변하고 $10^{5}$개의 질의를 처리해야 하므로 세그먼트 트리를 사용한다. 수입, 지출이 바뀌는 것이 아니라 추가되는 것이므로 갱신 연산을 수행할 때 이에 유의하도록 한다. 전체 코드 더보기 #include using namespace std; using ll = long long; int n, q; ll ar[1000001]; inline int mid(int stt, int end) { return stt + (end - stt) / 2; } void update(vector &tree, int node, int start, int end, int idx, ll diff) { if (idx > end || id..
백준 14438 - 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 배열의 값을 바꾸고 특정 구간의 최솟값을 물어보는 질의가 최대 10만건 들어온다. 세그먼트 트리를 통해 구간의 최솟값을 빠르게 계산하면 된다. 구간의 최솟값을 구할 때 구간을 벗어나는 범위는 INF로 처리해주면 된다. 전체 코드 더보기 #include using namespace std; int ar[100001]; int n; inline int mid(int stt, int end) { return stt + (end - stt) / 2; } int init(vector &tree, int node, int start, int end) { if (start == end) return tree[node] = ar[start]; int ..

티스토리툴바