컴공생 일상 블로그 컴공생 일상 블로그

문제https://www.acmicpc.net/problem/24024 풀이X개 이하의 스푼을 사용했을 때, 최소 비용의 최대 값을 구해야 함조금 생각해보면, X 스푼을 사용했을 때가 최소 비용의 최대 값임을 알 수 있다.정확한 그래프 개형은 몰라도, 특정 값에서 최대가 되는 그래프를 그리기 때문에, 빨간색 면에 대해 n 스푼, 파란색 면에 대해 X-n 스푼으로 삼분 탐색을 돌려주면 된다. 코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M, X;struct Input { int n; long long cost; int color;};struct Node {..

문제https://www.acmicpc.net/problem/13310 풀이캘리퍼스 + 삼분 탐색각 시간마다 찍힌 별들 중 최대 거리에 대해 최소값을 찾는 문제f(x)에 대한 삼분 탐색이지만 f(x)가 캘리퍼스 구현 ㅇㅇ..., distance 반환값을 int로 해놓고 발견못해서 고통받았다. + 계속 틀리길래 혹시해서 탐색 구현을 아래처럼 변경했더니 pass됨, 왜 그런지는 좀 생각해봐야 할듯// 틀림if (sim(lm) sim(rm)) { left = lm;}else { right = rm;}  코드#include #include #include #include #include #include #include using namespace std;struct Input { long long x, y, ..

문제https://www.acmicpc.net/problem/3679 풀이오랫만에 보는 Convex hull...? 비슷한 문제원래는 스택에 하나씩 push/pop하면서 Convex hull을 구해줘야하는데, 이는 모든 점을 사용해서 다각형을 만들어 주기만 하면 된다. 시작점0을 기준으로 반시계 기준으로 정렬하고 점을 차례로 이으면 좌측(N=5)그림과 같이 다각형을 그릴 수 있다.하지만 우측(N=7)그림과 같이 마지막 점들이 직선을 이루고 있는 경우 역순으로 이어줘야한다.이경우만 잘 고려해서 cross(0, N - 1, index)가 0일 경우부터는 역순으로 이어주면된다. 코드#include #include #include #include #include #include using namespace st..

문제https://www.acmicpc.net/problem/12752 풀이특별한 알고리즘은 없고, 단순 다익스트라 문제이다.많은 도시들이 있고 그 중 K(K   1. K = 1도로가 필요 없음  2. K = 2두 개의 도시를 연결하는 최소 비용을 구하면 된다. 간단하게 다익스트라 1번으로 구할 수 있다.  3. K = 3아래와 같은 경우들이 있을 수 있다. 각 점에서 출발해서 어떤 점에서 만난다고 생각하면 쉽다. K개의 도시(0, 1, 2 정점) N개의 정점에서 만나는 경우 중 비용 합의 최소 값을 구한다.A정점에서 만나는 경우: cost[0][A] + cost[1][A] + cost[2][A]B정점에서 만나는 경우: cost[0][B] + cost[1][B] + cost[2][B]...  4. K =..

문제https://www.acmicpc.net/problem/5670 풀이Trie: https://doraeul19.tistory.com/415전형적인 트라이 문제, 근데 입출력 형식이 여러개의 TC이므로 while(cin >> N)으로 입력받자Insert함수를 구현해서 트리를 잘 만들어주고, Find함수에서 자판을 눌러야하는 횟수를 더해가면 된다. 자판을 눌러야 하는 경우1. 맨 처음 글자: 첫 번째 글자는 무조건 눌러야 한다.2. 다른 문자열과 구분되지 않는 경우    - 현재 문자가 isEnd(다른 문자열의 끝인 경우)    - 다음 문자로 올 수 있는 경우가 2개 이상인 경우 코드#include #include #include #include #include #include #include #in..

문제https://www.acmicpc.net/problem/1854 풀이방법만 알면 쉬운 문제, k 번째의 최단 거리를 구하면 된다.기본 다익스트라를 조금 변형하면 된다.우선순위 큐에 거리를 push하면서 진행하면 된다. K  코드더보기#include #include #include #include #include #include #include #include #include #include using namespace std;int N, M, K;struct Node { int n; long long c; bool operator o.c; }};vector graph[1001];priority_queue pq;priority_queue ret[1001];int main() { ios::sync_wi..

문제https://www.acmicpc.net/problem/11437  설명문제 이름부터 나 LCA 문제입니다. 라고 하고 있는 문제시간 제한도 3초라 O(N)에 대해 돌면서 조상을 구해도 문제 없다.구현자체는 트리에서 level을 구하고 서로 만날 때 까지 올라가면 된다.  parse table에 부모를 저장하면서 O(logN)으로 돌 수 있는데, 이 부분은 나중에 다시...   코드#include #include #include #include #include #include #include using namespace std;int N, M;vector graph[50001];int level[50001];int parent[50001];queue q;void lca(int a, int b) { ..

문제https://www.acmicpc.net/problem/2679Network Flow + DFS  'A에서 B로 가는 중복 비율은 A에서 B로 가는 모든 길을 동시에 이용했을 때 1시간 동안 B에 도착할 수 있는 차의 최대 개수와 길 1개를 이용했을 때 도착할 수 있는 최대 개수의 비율이다.' A. A에서 B로 가는 모든 길을 동시에 이용하는 경우B. 길 1개를 이용했을 때 도착할 수 있는 경우A / B를 구하시오. 원문이 번역된 문제라, 뭔 소리인가 몇 번 읽어봤다. A는 최대유량을 구하라는 의미이고, B는 최대유량으로 구해지는 source->sink의 경로 중 하나에 대한 최대유량을 의미한다. B의 경우에는 최대유량, 다익스트라 돌려보다 결국 DFS로 다 돌렸다.해당 길을 이루는 간선들 중 최소..