-
[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 사이의 각을 세타라고 하자. 삼각함수를 이용해서 식을...
-
[BOJ] 8091 : Petrol
8091 : Petrol 풀이 KOI 주유소 문제에 자동차 연로탱크의 capacity가 추가된 버전(?) (사실 주유소 문제가 기억 안 나서 맞는지는 모름) 암튼 비슷하다. 시작점에서 끝점까지의 거리가 100만밖에 되지 않는다는 사실! 아하! 그렇다면 시작점으로부터의 거리를 인덱스로 삼는 배열을 하나 만들 수 있겠군! 오, 그럼 자동차를 한 칸씩 움직이면서 연료 탱크 최대값과 가능한 범위 내의 최소 기름값을 잘 관리하면 풀 수 있겠군!! 음… 근데 문제 분류를 어떻게 해야할지 모르겠군 코드 #include <cstdio> #include <queue> using namespace std; int...
-
[BOJ] 8088 : Airports
8088 : Airports 풀이 n개의 노드에 대해, 각 노드의 degree가 주어진다. 주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다. (불가능한 경우는 주어지지 않는다) 남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자. 이런 작업을 degree가 0이 될 때까지 반복하자. 다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다. 그럼 된다. 증명(?) 주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자. 그래프 G에서 degree가 가장...