-
[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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1414 : 불우이웃돕기
1414 : 불우이웃돕기 풀이 미니멈 스패닝 트리를 쓰자. 크루스칼을 쓰자. 전체 랜선의 합에서 최소로 잇는 랜선의 합을 빼주자. 자잘한 처리가 조금 귀찮은 문제다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct edg { int x, y, w; edg(int x, int y, int w) :x(x), y(y), w(w) {} bool operator <(edg A)const { return w < A.w; } }; int n, pnt[101]; vector<edg> gph; int find(int u) { if (u == pnt[u]) return...