-
[BOJ] 16172 : 나는 친구가 적다 (Large)
16172 : 나는 친구가 적다 (Large) 풀이 kmp 잘 짜주면 된다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j - 1]; if (p[i]...
-
[BOJ] 16171 : 나는 친구가 적다 (Small)
16171 : 나는 친구가 적다 (Small) 풀이 잘 짜주면 된다. 근데 그냥 16172번 복붙했다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j -...
-
[BOJ] 16169 : 수행 시간
16169 : 수행 시간 풀이 위상정렬 acm craft인가 그 문제랑 똑같은 것 같다. (사실 기억 안 남 ㅎ) 잘 짜주면 된다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, dap, l[101], t[101], d[101], r[101]; struct edg { int idx, dst; }; vector<edg> gph[101]; void go(int now) { dap = max(dap, r[now]); for (edg nxt : gph[now]) { r[nxt.idx] = max(r[nxt.idx], r[now] + t[nxt.idx] + nxt.dst); if (!(--d[nxt.idx])) go(nxt.idx); } } int...
-
[BOJ] 16168 : 퍼레이드
16168 : 퍼레이드 풀이 degree 짝수가 어쩌구 저쩌구 해서 풀어도 되는데 그냥 제곱 돌려도 된다. 근데 degree 어쩌구 저쩌구 할 때 유의해야 할 점은 connected graph가 아닐 수도 있어서 유니온파인드 같은 걸 해줘야한다. 잘 짜주면 된다. 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[3003][3003]; vector<int> gph[3003]; void dfs(int now, int num, int cnt) { if (cnt == m) { puts("YES"); exit(0); } for (int nxt : gph[now]) { if...
-
[BOJ] 16167 : A Great Way
16167 : A Great Way 풀이 잘 짜주면 된다. 코드 #include <cstdio> #include <queue> #include <vector> #define fst first #define snd second using namespace std; int n, m; struct abc { int idx, cst; }; vector<abc> gph[101]; pair<int, int> dp[101]; int main() { scanf("%d %d", &n, &m); while (m--) { int a, b, c, d, e; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); if (e > 10) c += ((e-10)*d); gph[a].push_back({ b,c...
-
[BOJ] 16166 : 서울의 지하철
16166 : 서울의 지하철 풀이 잘 짜주면 된다. 비트마스크 썼다. 코드 #include <cstdio> #include <queue> #include <map> using namespace std; int n, en; struct abc { int idx, hosun, cnt; bool operator <(abc a)const { return cnt > a.cnt; } }; map<pair<int, int>, int> cnt; map<int, int> subway; int main() { scanf("%d", &n); for (int i = 1, k; i <= n; i++) { scanf("%d", &k); for (int j = 0, x; j < k;...
-
[BOJ] 16165 : 걸그룹 마스터 준석이
16165 : 걸그룹 마스터 준석이 풀이 잘 짜주면 된다. 코드 #include <iostream> #include <string> #include <map> using namespace std; int n, m, num; string grp, str; map<string, string> mp; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; while (n--) { cin >> grp >> num; while (num--) { cin >> str; mp[grp] = str; mp[str] = grp; } } while (m--) { cin >> str >> num; if (!num) for (auto it :...
-
[BOJ] 8073 : Road Net
8073 : Road Net 풀이 인접행렬이 주어질 때, 다음과 같은 식 AB=AC+CB을 만족하는 경우가 있는지를 판별하면 된다. 음… 짜면 된다. 코드 #include <cstdio> int n, i, j, k, f, a[202][202]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]); for (i = 0; i < n; i++) for (j = i+1; j < n; j++) { f = 0; for (k...
-
[BOJ] 8103 : Rooks
8103 : Rooks 풀이 요약: n*n의 체스판에 n개의 룩을 배치해야 하는데, 어떤 룩도 서로를 잡을 수 없도록 배치해야한다. 그런데 그냥 배치하는 건 아니고, 각각의 룩을 배치할 수 있는 어떤 직사각형의 영역이 n개 주어진다. 각각의 룩은 각각의 영역 내에만 배치될 수 있다. 룩은 가로/세로로만 움직일 수 있다는 사실을 조금 관찰해보면, 답을 구하는 데 있어 가로 좌표와 세로 좌표가 독립적임을 알 수 있다. 즉, 한 축(가로 또는 세로)에 대해 조건에 맞게 배치하는 일을 두 번 해주고, 나중에...
-
[BOJ] 8101 : Rods
8101 : Rods 풀이 요약: 양 끝점이 고정된 길이 L의 선분이 있다. 이 선분의 가운데를 이쁘게 늘려서 길이 L+d의 곡선을 만든다. 그럼 길이 L의 현과 길이 L+d의 호가 만들어진다. 이 때, 현의 중심과 호의 중심까지의 거리 x는 얼마일까? 알고리즘에 수학을 싸서 드셔보세요!! 주어진 호를 예쁘게 연장해서 예쁜 원을 만들어주자. 원의 중심에서 현의 끝점까지 예쁜 반지름 r1, r2도 그어주자. 현을 이등분하는 예쁜 반지름 r3도 그어주자. r3와 r2, r3와 r1 사이의 각을 세타라고 하자. 삼각함수를 이용해서 식을...