문제 백준 9694번 풀이 0번 정점(한신이)부터 최고의원을 만나기까지 친밀도의 합을 최소화하려면 최단 경로를 구하는 알고리즘을 사용하면 됩니다. 0번 정점을 시작 정점으로 잡아두고 다익스트라를 돌려주고, 각 정점을 갱신할 때마다 방문했던 정점들을 업데이트하면 쉽게 풀 수 있습니다. $ T $가 $ 100 $ 미만이고 $ N $이 $ 20 $ 이하이므로 플로이드-워셜(Floyd-Warshall)을 사용하더라도 $ O(TN^3) $에 풀릴 것 같습니다. 소스코드 #include using namespace std; typedef pair pii; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int t; cin >> t; for (int i = 1;..

문제 백준 17612번 풀이 정해는 우선순위 큐를 사용하는 것이지만 $ N $의 크기가 작기 때문에 단순 구현으로 풀 수 있는 문제입니다. 기다리는 고객들을 큐로 관리하고 계산대에 있는 고객들을 벡터로 관리합니다. 계산대에 있는 고객들 중 남은 물건 수의 최솟값을 $ M $이라 두면, 계산대를 순회하면서 모든 고객의 물건을 $ M $개씩 빼서 $ 0 $이 되면 쇼핑몰을 빠져나오는 벡터에($ exit $) 넣어주고 빈 자리에는 기다리는 고객들의 큐에서 하나를 빼서 넣어줍니다. 나오는 순서는 계산대 번호가 큰 순서대로지만, 순회는 작은 숫자부터 했기 때문에 $ exit $을 뒤에서부터 처리해서 답을 구해주면 됩니다. 소스코드 #include using namespace std; typedef unsigned..

문제 백준 4195번 풀이 Union Find를 구현하여 해당 집합에 몇 개의 원소가 속하는지는 개수를 관리하는 배열을 하나 더 만들어주면 됩니다. 관리해야 할 원소가 string이여서 까다롭기 때문에 이 문제가 Gold II(solved 기준)이지 않을까 생각합니다. C++에서는 unordered_map이라는 자료구조를 사용하여 $ mp[string] = int $라고 두면, 이론상 $ O(1) $로 각 유저의 string에 대해서 UF의 원소 int를 가져올 수 있습니다. (unordered_map mp) map이 마음에 안든다 싶으면.. set 등으로 이진 탐색을 사용하는 $ O(log N) $짜리 테이블도 만들 수 있을 것 같습니다. UF에서 개수를 구하는 구현은 코드가 쉽기 때문에 설명은 생략합..

문제 백준 15976번 풀이 문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다. $ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다. 문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다. 누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다. 문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께..

문제 백준 1226번 풀이 솔직히 문제 번역본이 그렇게 좋은 것 같진 않습니다. $ N $개의 정당 중 $ K $개의 정당을 뽑아서 연합을 만들 수 있습니다. ($ A_{i} $: $ i $번째 정당의 인원수) 이 연합에 속한 정당의 인원들의 합이 전체 정당의 인원수($ \sum_{i=1}^n A_{i} $)의 절반 이상이어야 하며, 연합 중 임의의 한 정당을 뺐을 때 연합의 인원수의 합이 전체 정당의 인원수의 반 미만이 되는 것을 모두 만족해야 합니다. 위 조건을 모두 만족하는 연합 중 가장 많은 인원수를 가지는 연합을 찾는 문제입니다. 문제를 그리디로 접근하면, 정당의 인원수가 많은 것부터 보면서, 전체 정당의 인원수의 절반($ \frac{(\sum_{i=1}^n A_{i})}{2} $)을 처음으로 ..

문제 백준 14867번 풀이 $ F, E, M $ 연산을 실행하며, 물통에 $ C, D $가 담겨있도록 만드는 최솟값을 구하려면, BFS(너비 우선 탐색)를 사용하면 됩니다. 이미 방문한 정점인지 확인하는 것은 map을 사용하면 쉽게 처리할 수 있습니다. $ F, E, M $ 연산 구현만 유의하면 쉽게 풀 수 있습니다. 소스코드 #include #include #include #include using namespace std; typedef pair pii; unordered_map vis; int ans = -1; int a, b, ta, tb; queue q; void F(int ca, int cb) { if (!vis[a][cb]) { vis[a][cb] = vis[ca][cb] + 1; q.pu..