-
[BOJ] 8088 : Airports
8088 : Airports 풀이 n개의 노드에 대해, 각 노드의 degree가 주어진다. 주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다. (불가능한 경우는 주어지지 않는다) 남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자. 이런 작업을 degree가 0이 될 때까지 반복하자. 다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다. 그럼 된다. 증명(?) 주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자. 그래프 G에서 degree가 가장...
-
[BOJ] 8093 : Credibility of Witnesses
8093 : Credibility of Witnesses 풀이 믿는다의 정의는 재귀적인데, 1. A는 A를 믿는다, 입력으로 주어진 쌍에 있는 사람들도 믿는다. 2. A가 B를 믿는다면, A는 B가 믿는 모든 사람들을 믿는다. 믿지 않는다의 정의도 재귀적인데, 1. A는 입력으로 주어진 쌍에 있는 사람들을 믿지 않는다. 2. A가 B를 믿는다면, A는 B가 믿지 않는 모든 사람들을 믿지 않는다. 그래서 모든 A에 대해서, A가 믿으면서 믿지 않는 B가 존재하는지 찾는 문제입니다. - said koosaga dfs를 n번 돌려서 O(n^2) 정도에 풀...
-
[BOJ] 8098 : Lecture Halls Reservation
8098 : Lecture Halls Reservation 풀이 회의실 배정이랑 비슷하게 생겼다. 오… 이거 데이터 생겨먹은 게 끝나는 시간을 기준으로 정렬해주고 싶게 생겼다. 시간의 최대 범위가 3만이므로, 각각의 시간에 대해, 해당 시간까지의 최대 해를 계산해줄 수 있다. 약간 다이나믹스러운 느낌으로 d[time] = max(d[time], d[start]+end-start) 주어진 구간의 양 끝점만 보고 삭 긁어주면 된다. 시간 범위가 3만보다 (엄청) 크다면 세그트리 등등을 이용해서 풀어줄 수 있겠다. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, r, d[30003]; pair<int, int>...
-
[BOJ] 8095 : The Number of N-k-special Sets
8095 : The Number of N-k-special Sets 풀이 1부터 N까지의 정수를 최대 한 번씩 사용하는데, 인접한 숫자를 사용하지 않고, k이상의 정수를 만드는 경우의 수를 구해야한다. 딱 문제가 저는 다이나믹이에요!!!! 라고 소리지르고 있다. 나는 두 가지 방법으로 풀었다. 아 그리고 답이 long long 범위마저 넘어가므로 Big Integer스러운 어떤 방법이나 언어를 잘 골라서 구현해야 한다. 방법1 dp[i][k] = 1~i를 사용해서 k를 만드는 경우의 수 i-1(인접하면 안 되니까 i-1)보다 작은 j들에 대해, dp[j][k-i]를 누적하여 세어주면 어렵지 않게 계산할...
-
[BOJ] 8094 : Canoes
8094 : Canoes 풀이 투포인터(?) 같은 느낌으로 그리디하게 풀어주자. 각 카누들의 용량(?)을 정렬해주자. 정렬 후 배열의 양 끝에는 min, max 값이 들어있으므로 양 사이드에서 가운대로 포인터를 옮기며 매칭할 수 있다면 매칭해주자. 코드 #include <cstdio> #include <algorithm> int n, w, i, j, a[30003]; int main() { scanf("%d %d", &w, &n); for (; j<n; j++) scanf("%d", &a[j]); std::sort(a, a+n); for (j = n-1; j && i<j; j--) if (a[i]+a[j]<=w) i++; printf("%d", n-i); return 0; } 아무말 백준,...