-
[BOJ] 14572 : 스터디 그룹
14572 : 스터디 그룹 풀이 학생들이 아는 모든 알고리즘의 수는 bit OR 연산과 같다. 이는 항상 같거나 증가한다. 모든 학생들이 아는 알고리즘의 수는 bit AND 연산과 같다. 이는 항상 같거나 감소한다. 따라서 누구는 빼고 누구는 넣고 할 것 없이 능력치 조건을 만족하는 범위 내의 모든 학생들을 선택해도 된다. 학생들을 능력치를 기준으로 정렬한 다음, 투 포인터를 사용하면 쉽게 답을 찾을 수 있다. 코드 #include <stdio.h> #include <algorithm> using namespace std; const int n_ = 1e5 +...
-
[BOJ] 14571 : 모래시계
14571 : 모래시계 풀이 임의의 두 인접한 사이클은 하나 또는 두개의 노드를 공유할 수 있으므로 두 경우의 수를 모두 구해서 겹치는 경우를 제거하자 컴비네이션으로 구하면 쉽게 구할 수 있다. 코드 #include <stdio.h> #include <vector> using namespace std; typedef long long ll; const int n_ = 200; int n, m, one[n_], two[n_][n_]; bool gph[n_][n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d",...
-
[BOJ] 14570 : 나무 위의 구슬
14570 : 나무 위의 구슬 풀이 문제의 조건을 그대로 가져다 써보자. 모든 노드에 대해, 왼쪽 구슬의 수가 오른쪽 구슬의 수보다 크거나 같다. n개의 구슬 중 n/2+n%2개는 왼쪽, n/2개는 오른쪽으로 떨어지게 된다. 종단 노드를 만날 때 까지 돌려보자~~ 코드 #include <stdio.h> struct hello { int l, r; } t[200001]; int main() { int n; long long k; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].l, &t[i].r); scanf("%lld", &k); int cur...
-
[BOJ] 14569 : 시간표 짜기
14569 : 시간표 짜기 풀이 모든 경우를 다 돌려보면 된다. bit를 사용하면 편하게 짤 수 있다. 코드 #include <stdio.h> typedef unsigned long long ull; ull t[1001]; int main() { int n, m, k; scanf("%d", &n); for (int i = 0; i < n; i++) { int k, a; scanf("%d", &k); for (int j = 0; j < k; j++) scanf("%d", &a), t[i] |= ((ull)1 << a); } scanf("%d", &m); for (int i = 0; i...
-
[BOJ] 14568 : 2017 연세대학교 프로그래밍 경시대회
14568 : 2017 연세대학교 프로그래밍 경시대회 풀이 택희가 받는 사탕의 개수를 i로 두고 구하면 된다. n개 사탕 중에서 택희 사탕 i개와 영훈이랑 남규의 사탕 차이 2개를 뺀 사탕 갯수 n-i-2에서 (영훈 <= 남규)를 만족하는 조합의 수는 (n-i-2)/2와 같다. ex1) 5를 나누는 경우: (1,4), (2,3) ex2) 6를 나누는 경우: (1,5), (2,4), (3,3) 코드 #include <stdio.h> int n, sum; int main() { scanf("%d", &n); for (int i = 2; i <= n - 2; i += 2)...