문제 백준 1806번 풀이 투포인터, 누적합(map), 분할정복을 사용하여 풀 수 있습니다. 이 문제의 경우 배열의 모든 원소가 자연수이므로 투포인터 풀이도 가능합니다. 왼쪽(l), 오른쪽(r) 변수와 l ~ r 사이의 합을 저장하는 sum 변수를 만들어 문제의 조건에 맞게 l과 r을 관리하면 됩니다. * sum이 S(문제에서 주어지는 것)보다 크거나 같으면 left를 한칸 오른쪽으로 옮깁니다. * 그렇지 않으면 right를 오른쪽으로 옮깁니다. - 위 과정을 l과 r 모두 n - 1이 될 때까지 반복합니다. 소스코드 #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int n, s, ans = 1..

문제 백준 12930번 12930번: 두 가중치 0번 정점에서 1번 정점으로 가는 최단 경로의 비용을 출력한다. 0번에서 1번으로 갈 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 조건이 복잡한 다익스트라입니다. priority queue에 cost, 현재 정점, 가중치 1의 합, 가중치 2의 합을 저장해두고 매번 갱신해주면 됩니다. 소스코드 #include using namespace std; typedef long long ll; typedef pair ppll; ll dist[21], graph[21][21][2]; vector _node[21]; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; for (int t..

문제 백준 1197번 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net 크루스칼 알고리즘 3 3 1 2 1 2 3 2 1 3 3 테스트 케이스의 내용을 시각화하면 아래와 같습니다. 트리 구조를 유지하되, 간선의 가중치를 최소화하려면 (1, 3)의 간선을 제거하면 됩니다. ​ 크루스칼 알고리즘은 최소 비용 신장 트리를 찾는 알고리즘입니다. 작동 방법을 설명하기 위해 아래 그래프의 최소 스패닝 트리를 구해보겠습니다. 우선, 간선의 가중치가 오름차순이 되도록 정렬을 ..

문제 한국정보올림피아드 2013년 고등부 1번 백준 8983번 풀이 사대의 위치와 동물의 위치 간의 거리는 x좌표의 차이와 동물의 y좌표를 더한 값입니다. 또한, 사대는 x축 위에 있기 때문에 y좌표는 어느 사대를 선택하던 변하지 않습니다. 즉, 동물과 가장 가까운 사대를 구하려면 x좌표의 차이가 최소가 되는 사대를 찾으면 됩니다. 동물의 수와 사냥꾼의 수가 최대 100,000이므로 각 동물에 대한 최적의 위치에 있는 사대를 찾을 때 완전 탐색을 하면 TLE가 납니다. 가장 가까운 사대를 찾기 위해 동물의 x 좌표에 대한 이분 탐색을 해봅시다. 이 때, lower_bound를 사용하는 경우 사대의 후보가 2개가 나옵니다. 이 경우에는 lower_bound로 선택된 사대가 정답입니다. 하지만 아래의 경우에..

문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..