-
[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)...
-
[BOJ] 13910 : 개업
13910 : 개업 풀이 웍을 최대 2개까지 사용할 수 있으므로 가능한 조합을 모두 구해둔다 그리고 점화식 세워서 풀면 된다. dp[n] = min(dp[n-i]+1,dp[n]) 코드 #include <stdio.h> int main() { int n, m, i, j, a[101], dp[10001]; bool chk[22222] = { 0 }; scanf("%d %d", &n, &m); for (i = 0; i <= n; i++) dp[i] = 1e9; chk[0] = 1; dp[0] = 0; for (i = 0; i < m; i++) scanf("%d", &a[i]); for (i =...
-
[BOJ] 2583 : 영역 구하기
2583 : 영역 구하기 풀이 직사각형 영역에 체크를 해놓고 모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다. 입력이 좀 짜증난다 (…) 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; int n, m, k, cnt, a[111][111]; vector<int> v; int dfs(int x, int y) { int ret = 1; a[x][y] = 1; for (int i = 0; i < 4; i++)...
-
Maidas Challenge 2017 온라인 예선 풀이
원래 나도 대회 참가하려고 했었는데 귀찮아서 대회 접수를 까먹어버렸다 ㅋㅋ;; 빨리 접수하라고 전화까지 왔었는데 흑 대충 문제만 듣고 풀어보았다. 문제 풀이 순서는 내 맘대로 ㅎㅎ 1. Maidas Number 풀이 1에서 n까지의 자연수들 중에서 소인수의 최대값이 m보다 작은 수의 갯수를 세는 문제이다. 일단 소인수는 모두 소수이므로 소수를 구해둔 뒤 모든 1~n 자연수를 검사해주면 된다. 어떤 자연수 k에 대해 m 이상의 소수를 약수로 가진다면 이는 조건에 불일치하는 것이므로 컷 해주면 된다. 제한시간이 10초인 걸로 아는데 음… 내가...
-
[BOJ] 1107 : 리모컨
1107 : 리모컨 풀이 그냥 다 돌려보자! 코드 #include <stdio.h> int n, m, i, k, ans, res; bool chk[10]; int hi(int a) { int cnt = 0; while (a) { if (chk[a % 10]) return -1; a /= 10; cnt++; } return cnt; } int main() { scanf("%d %d", &n, &m); for (i = 0; i < m; i++) scanf("%d", &k), chk[k] = true; ans = n - 100; if (ans < 0) ans =...
-
[BOJ] 2010 : 플러그
2010 : 플러그 풀이 새로운 멀티탭의 플러그 수에서 하나를 뺀 값을 더해주면 된다. 코드 #include <stdio.h> int main() { int n, i, k, sum = 1; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&k); sum += k-1; } printf("%d",sum); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이