-
[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 :...
-
[일상] 웹알못 블로거의 신나는 웹 코딩
약 2시간 정도 삽질했는데, 결론부터 말하자면 구현은 실패 했다. 아이 신난다 사실 이 블로그가 카카오 테크 블로그에서 따온 블로그인데, 원래 검색 기능은 이렇게 구현되어 있었다: $('#search').submit(function (e) { e.preventDefault(); var q = $('#searchQueryEdit').val(); var url = 'http://search.daum.net/search?q=' + encodeURIComponent(q + ' site:tech.kakao.com'); window.open(url, '', '_blank'); }); 아니 무려 카카오에서 일하시는 분들이 검색을 짜기가 귀찮아서 웹으로 넘겼다고? 그럼 내가 한 번 해보지! 잘은 모르지만 대충 배껴서 만들면 아마 돌아갈거야 재앙의 시작 룰루 랄라~ ...
-
[BOJ] 1992 : 쿼드트리
1992 : 쿼드트리 풀이 분할정복을 하자 네모 크기가 1일 떄 까지 내려갔다가 올라오자 코드 #include <stdio.h> int n; char a[65][65]; void gogo(int x1, int y1, int x2, int y2) { char now = a[x1][y1]; if (x1 == x2 && y1 == y2) { printf("%c", now); return; } for (int i = x1; i < x2; ++i) { for (int j = y1; j < y2; ++j) { if (now != a[i][j]) { printf("("); gogo(x1, y1,...
-
[BOJ] 1753 : 최단경로
1753 : 최단경로 풀이 다익스트라를 짜자 우선순위 큐를 쓰자 코드 #include <stdio.h> #include <algorithm> #include <queue> #include <vector> using namespace std; const int v_ = 20000 + 1; const int INF = 987654321; struct edg { int idx, dst; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int v, e, s, dst[v_]; vector<edg> gph[v_]; void dijkstra() { for (int i = 0;...
-
[BOJ] 10844 : 쉬운 계단 수
10844 : 쉬운 계단 수 풀이 점화식을 세우자 dp[i][j] = 총 i 자릿수이고, 가장 큰 자릿수의 숫자가 j인 경우의 수 = dp[i-1][j-1] + dp[i-1][j+1] 끗! 코드 #include <stdio.h> const int mod = 1e9; int n, i, j, dp[101][11], ans; int main() { scanf("%d", &n); for (i = 1; i <= 9; ++i) dp[1][i] = 1; for (i = 2; i <= n; ++i) for (j = 0; j <= 9; ++j) dp[i][j] = (dp[i -...
-
[BOJ] 1260 : DFS와 BFS
1260 : DFS와 BFS 풀이 bfs를 돌리자! dfs도 돌리자! 코드 #include <cstdio> #include <queue> #include <cstring> using namespace std; int n, m, v, chk[1001], gph[1001][1001]; void dfs(int now) { chk[now] = 1; printf("%d ", now); for (int i = 1; i <= n; i++) if (!chk[i] && gph[now][i]) dfs(i); } void bfs(int now) { queue<int> que; que.push(now); chk[now] = 1; while (!que.empty()) { int now = que.front(); que.pop(); printf("%d ", now); for (int i =...
-
[BOJ] 1948 : 임계경로
1948 : 임계경로 풀이 문제를 다르게 생각해보자. 마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다. 따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다! 풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야 코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다. get_max_len() 함수를 보면 일단 카운팅하기 전에...