-
[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] 머그컵 풀이
문제: https://www.acmicpc.net/contest/view/213 많은 도움 주신 스타트링크께 감사드립니다! A. 준오는 심술쟁이!! BOJ 백준 14437 준오는 심술쟁이!! 제한시간이 1초이기 때문에 단순히 3000 * 3000 * 25 dp를 돌렸다간 시간초과를 받는다. dp[문자열길이][s의 합] 일 때, 문자열 길이를 p, s 합을 q라고 하면 dp[p][q] = k가 0 ~ min(q, 25)일 때의 모든 dp[p-1][q-k]의 합 으로 점화식을 세워 해결할 수 있다. #include <iostream> #include <string> #define min(x, y) ((x)<(y)?(x):(y)) using namespace std; typedef long long ll; const int MOD =...