본문 바로가기

백준

 (223)
백준 11444 - 피보나치 수 6 https://www.acmicpc.net/problem/11444 최대 $10^{18}$ 번째 피보나치 항을 구해야 한다. 피보나치 수의 n번째 항 $F_{n}$은 다음과 같은 행렬 제곱으로 나타낼 수 있음이 알려져있다. $\begin{pmatrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \end{pmatrix}^{n}$ 분할 정복을 이용한 거듭제곱을 활용하여 원하는 항을 빠르게 구하면 된다. 전체 코드 더보기 #include using namespace std; using ll = long long; ll mod = 1e9 + 7; ll n; struct mat_fibo { vector mat; mat_fibo(): mat(2, vector(2)) {} mat_fibo..
[ICPC] 백준 5676 - 음주 코딩 https://www.acmicpc.net/problem/5676 풀이 세트당 최대 10만개의 질의를 통해 구간 곱을 구하고 갱신하는 문제이다. 이를 처리하기 위해 세그먼트 트리를 생각해볼 수 있다. 다만 갱신하려는 구간에 0이 있는 경우 구간의 곱은 0이 되어 갱신할 때 어려움을 겪을 수 있다. 구간을 갱신할 때 먼저 리프 노드의 값을 바꿔주고 부모 노드에 이를 반영해주도록 하면 0이 포함된 구간은 문제 없이 처리할 수 있다. 문제에서는 값의 부호만 중요하므로 혹시 모를 오버플로우를 방지하기 위해 양수는 1, 음수는 -1로 통일하여 계산하도록 한다. 문제에서 요구하는 대로 출력하면 된다. 전체 코드 더보기 #include using namespace std; int ar[100001]; int n, k..
백준 2042 - 구간 합 구하기 https://www.acmicpc.net/problem/2268 입력으로 주어지는 수가 long long 범위에 있다는 사실에 유의하면서 세그먼트 트리 연산을 수행하면 된다. 전체 코드 더보기 #include using namespace std; using ll = long long; ll ar[1000001]; int n, m, k; inline int mid(int l, int r) { return l + (r - l) / 2; } ll init(vector &tree, int node, int start, int end) { if (start == end) return tree[node] = ar[start]; int m = mid(start, end); return tree[node] = ini..
백준 2268 - 수들의 합 https://www.acmicpc.net/problem/2268 최대 10만건의 구간 수정과 합을 구할 것을 요구하는 문제이다. 세그먼트 트리를 통해 원하는 질의를 빠르게 수행하면 된다. 배열의 초기 조건은 주어지지 않았으므로 세그먼트 트리를 초기화 할 필요 없이 sum과 update 연산만 구현하면 된다. 전체 코드 더보기 #include using namespace std; using ll = long long; int ar[1000000]; inline int mid(int l, int r) { return l + (r - l) / 2; } ll sum(vector &tree, int node, int stt, int end, int l, int r) { if (l end) return; tree..
[KOI] 백준 2644 - 촌수계산 https://www.acmicpc.net/problem/2644 가족 관계는 트리 형태를 가진다. 따라서 어떤 노드 A에서 B가 연결되어 있다면 그것은 단순 경로이다. 가족의 관계를 그래프로 구성하고 단순히 BFS를 통해 몇번 거쳐갔는지를 세면 된다. 원하는 노드를 찾지 못할 경우 -1을 출력하면 된다. 정답 코드 더보기 #include using namespace std; using pii = pair; int n; int mesh[101][101]; bool visited[101]; int a, b; int e; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> a >> b >> e; vector graph(n + 1); ..

티스토리툴바