-
[BOJ] 7662 : 이중 우선순위 큐
7662 : 이중 우선순위 큐 풀이 multiset을 써서 풀었는데 map으로 풀어도 될 거 같고 아무튼 그냥 짜면 된다. 코드 #include <iostream> #include <set> using namespace std; int main() { int t; cin >> t; while (t--) { int k; cin >> k; char c; int n; multiset<int> v; while (k--) { cin >> c >> n; if (c == 'I') { v.insert(n); } else if (c == 'D' && v.size() > 0) { if (n...
-
[BOJ] 4243 : 보안 업체
4243 : 보안 업체 풀이 내가 지금 [left, right] 구간을 방문한 상태라고 하면, 다음 상태는 [left-1, right] 또는 [left, right+1]가 될 것이다. 이를 토대로 다이나믹 프로그래밍을 해주자. 단, 다음 두 상태로 나아갈 때 left에 서있는지 right에 서있는지에 따라 거리합이 달라지므로 이를 유의해서 코드를 짜보자. 코드 #include <cstdio> #include <cstring> typedef long long ll; int tc, n, s, a[102]; ll dp[2][102][102]; ll min(ll a, ll b) { return a<b?a:b; } ll dst(int x, int y) {...
-
[BOJ] 1713 : 후보 추천하기
1713 : 후보 추천하기 풀이 짜라는대로 짜면 된다. 코드 #include <cstdio> #include <deque> #include <algorithm> using namespace std; int n, m; struct abc { int idx, vote, time; bool operator <(abc a)const { if (vote == a.vote) return time < a.time; return vote < a.vote; } }; int main() { deque<abc> d; scanf("%d %d", &m, &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); for (abc &it : d)...
-
[BOJ] 16120 : PPAP
16120 : PPAP 풀이 일반적인 괄호 문자열 문제랑 비슷하게 해결하면 된다. 코드 #include <cstdio> int t; char a[1000003], s[1000003]; int ppap() { if (t < 4) return 0; if (s[t-4]=='P'&&s[t-3]=='P'&&s[t-2]=='A'&&s[t-1]=='P') return 1; return 0; } int main() { scanf("%s", a); int cnt = 0; for (int i = 0; a[i]; i++) { s[t++] = a[i]; while (ppap()) t -= 4, s[t++] = 'P'; } puts(t == 1 && s[0] == 'P' ? "PPAP" : "NP");...
-
[BOJ] 16118 : 달빛 여우
16118 : 달빛 여우 풀이 다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데 if (dp[now] != current_sum) continue; 위와 같은 동작을 넣은 코드와 그렇지 않은 코드의 시간복잡도가 다르다. (자세히는 모름) 이 문제의 경우, 데이터가 엄청 빡세서 저 동작을 넣어주지 않으면 시간 초과를 받게 된다. 아래의 코드를 참고하자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; int n, m; struct edg { int idx, cnt; ll dst; bool operator...
-
[BOJ] 16113 : 시그널
16113 : 시그널 풀이 잘 짜면 된다 코드 #include <cstdio> #include <cstring> int n, r[100003]; char a[100003], s[20005][5]; int isone(int x) { for (int i = 0; i < 5; i++) if (s[x][i] == '.' || s[x+1][i] == '#') return 0; return 1; } int count(int x) { int ret = 0; for (int i = x; i < x+3; i++) for (int j = 0; j < 5; j++) ret += s[i][j] == '.';...
-
[BOJ] 16112 : 5차 전직
16112 : 5차 전직 풀이 메이플스토리~~ 코드 #include <cstdio> #include <algorithm> int n, k, a[300003]; long long r, s; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a+n); for (int i = n-1; i >= 0; i--) { if (i < k) r += s; s += (long long)a[i]; } printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge,...
-
[BOJ] 15267 : Justified Jungle
15267 : Justified Jungle 풀이 트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다. 즉, 노드는 n의 약수로만 나눠질 수 있다. 100만 이하 자연수의 약수 개수가 최대 240개니까 O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠… 아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다. 트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자. 음… 그냥 코드를 보는 게 더 빠르겠다. 코드 #include <cstdio> #include <vector> using namespace std; int n,...
-
[BOJ] 15264 : Gambling Guide
15264 : Gambling Guide 풀이 1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다! 그러니까 N에서부터 1로, 거꾸로 가면서 구해주자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int n_ = 3e5+3; int n, m, sdeg[n_]; double dp[n_], sdp[n_]; struct abc { int idx; double val; bool operator <(abc a)const { return val > a.val; } }; priority_queue<abc> pq; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for...
-
[BOJ] 14961 : Untangling Chain
14961 : Untangling Chain 풀이 가장 위, 가장 아래, 가장 오른쪽, 가장 왼쪽의 좌표를 기억해두자. 그리고 항상 그 좌표보다 한칸 더 위로 직선을 쏴주자. 혹은 내 코드처럼 같은 방향(시계, 반시계)으로 두 번 이상 전진하는 경우로 접근해도 된다. 코드 #include <cstdio> int n, i, now, prv; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) { printf("%d ", now-prv ? 1 : i); prv = now; scanf("%d %d", &now, &now); } return...