-
[잡담] ps와 cp에 대한 나의 경험과 생각
슬픈 이야기를 조금 해보려고 한다. 친구가 이런 글을 보내줬다. 그리고 그 글에는 이런 글도 링크되어 있었다. 글을 많이많이 요약하자면, Problem Solving과 Competitive Programming은 다르다. PS는 문제를 오래 고민하는 학문적인, CP는 빠른 시간안에 문제를 해결하는 경쟁적인 것. “저는 CP를 알고리즘 대회라고 보지 않습니다. 알고리즘 능력이 없으면 문제를 풀 수 없지만, 마찬가지로 코딩 능력도 같기 때문에, 결국 두 가지를 섞은 어딘가에 대회가 위치한다고 생각합니다.” 이런 내용인데 PS를 하고 있다면, 시작했다면, 시작하려고 한다면 한 번 쯤은 고민해봐도 좋을...
-
[BOJ] 14434 : 놀이기구1
14434 : 놀이기구1 풀이 머그컵 문제! parallel binary search를 사용하면 된다! 자세한 풀이는 여기에 있다. 헤헤 놀이기구2도 풀어봐야지 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int MAX = 2e5 + 3; int N, M, K, Q; int lim[MAX], ans[MAX]; vector<int> grow[MAX]; inline int get_sum(int u, int v, int k) { int ret1 = upper_bound(grow[u].begin(), grow[u].end(), k) - grow[u].begin(); int ret2 = upper_bound(grow[v].begin(), grow[v].end(), k) - grow[v].begin(); return ret1 + ret2; }...
-
[BOJ] 1162 : 도로포장
1162 : 도로포장 풀이 dp[노드번호i][포장갯수k]로 놓고 다익스트라를 돌리자! 원래 다익스트라에서 사용하던 dist[i]대신 dp[i][j]를 참조하면서 돌면 된다. now.dst는 지금까지 누적해 온 dst값이고, nxt.dst는 노드 사이의 거리(가중치)이다. 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int n_ = 10000 + 1; struct edg { int idx, dst, cnt; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool...
-
[BOJ] 13209 : 검역소
13209 : 검역소 풀이 이분 탐색(log n)을 돌면서 그리디(n)을 돌리면 O(n log n)에 해결할 수 있다. priority_queue를 사용하기 전에 벡터를 써서 정렬하는 생각을 먼저 했지만 코딩이 괴랄해져서 포기하고 우선순위큐를 사용했다. 바이너리 서치의 mid를 비축할 백신의 수라고 두고, 주어진 검역소만으로 mid를 충족시킬 수 있는지 그리디로 풀면 된다. 싸이클이 없고 임의의 a에서 b로 가는 경로가 단 하나이기 때문에 그리디로 풀 수 있다! dfs의 리턴값은 항상 mid를 넘지 않음이 보장된다. 물론 인구수가 mid를 넘을 수는 있다. 그건 left...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...