-
[BOJ] 10610 : 30
10610 : 30 풀이 어떤 숫자 N이 3의 배수인 조건 : 모든 자리에 있는 숫자들의 합이 3의 배수 10의 배수인 조건 : 첫째 자리의 숫자가 0 이 둘을 합쳐주면 30인 조건이 된다 (!!!) 코드 #include <stdio.h> int i, sum, cnt[10]; char str[100002]; int main() { scanf("%s", str); for (i = 0; str[i]; i++) cnt[str[i] - '0']++, sum += str[i] - '0'; if (!cnt[0] || sum % 3) return ~printf("-1"); for (i = 9; i >=...
-
[BOJ] 11725 : 트리의 부모 찾기
11725 : 트리의 부모 찾기 풀이 별 하나에 추억과 별 하나에 사랑과 별 하나에 쓸쓸함과 별 하나에 동경(憧憬)과 별 하나에 시와 별 하나에 어머니, 어머니 코드 #include <stdio.h> #include <vector> using namespace std; int n, pnt[100001]; vector<int> gph[100001]; void dfs(int now) { for (int nxt : gph[now]) if (pnt[now] ^ nxt) pnt[nxt] = now, dfs(nxt); } int main() { scanf("%d", &n); for (int i = 0, u, v; i < n - 1; i++) {...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 리프 노드라는 것은, 들어오는 간선이 없다는 것. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return ~printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now ==...
-
[BOJ] 1967 : 트리의 지름
1967 : 트리의 지름 풀이 트리에서 임의의 노드 ㄱ을 고른 뒤 ㄱ에서 가장 먼 노드 ㄴ을 찾고 ㄴ에서 가장 먼 노드 ㄷ을 찾으면 ㄴ과 ㄷ이 트리의 지름이 된다 (!) 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 4; struct edg { int idx, dst; }; int n, abc, sum; vector<edg> gph[n_]; void dfs(int prv, int now, int dst) { if (sum < dst) sum = dst, abc...
-
[BOJ] 1562 : 계단 수
1562 : 계단 수 풀이 D[length][number][bitmask] = D[length - 1][number ± 1][bitmask | (1 << number)] 룰루랄라 코딩을 해보자~ 코드 #include <stdio.h> #include <string.h> const int mod = 1e9; int n, ans, dp[101][10][1025]; int dfs(int len, int num, int msk) { int &ret = dp[len][num][msk]; msk |= (1 << num); if (num < 0 || num > 9) return 0; if (len == n) return (msk == (1 << 10) - 1) ? 1 :...
-
[BOJ] 1693 : 트리 색칠하기
1693 : 트리 색칠하기 풀이 http://codersbrunch.blogspot.kr/2017/07/1693.html 읽고 구현한 코드입니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e5 + 5; int n, dp[n_][18]; vector<int> gph[n_]; void dfs(int prv, int now) { dp[now][0] = 2e9; for (int col = 1; col <= 17; col++) dp[now][col] += col; for (int nxt : gph[now]) { if (nxt == prv) continue; dfs(now, nxt); int fst = 0, snd = 0; for (int col...
-
[BOJ] 2798 : 블랙잭
2798 : 블랙잭 풀이 퇴근 하고 싶다 코드 #include <stdio.h> int n, m, i, j, k, a[101], ans; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (i = 0; i < n; i++) for (j = 0; j < n; j++) for (k = 0; k < n; k++) if (i != j && j != k && k != i) { int t...
-
[BOJ] 1727 : 커플 만들기
1727 : 커플 만들기 풀이 D[n][m] = 오름차순으로 남자 n명, 여자 m명을 짝짓는 최소의 값 D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n-1][m]) (if n > m) D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n][m-1]) (if n < m) 코드 #include <stdio.h> #include <algorithm> using namespace std; int abs(int a) { return a < 0 ? -a : a; } int n, m, a[1001], b[1001], d[1001][1001]; int main() { scanf("%d %d", &n, &m); for (int...
-
[BOJ] 11724 : 연결 요소의 개수
11724 : 연결 요소의 개수 풀이 느낌있게 깊이우선탐색 코드 #include <iostream> #include <vector> using namespace std; int n, m, ans, vst[1001]; vector<int> gph[1001]; void dfs(int now) { vst[now] = 1; for (int nxt : gph[now]) if (!vst[nxt]) dfs(nxt); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; for (int i = 0, u, v; i < m; i++) { cin >> u >> v; gph[u].push_back(v), gph[v].push_back(u); } for (int i = 1; i <=...
-
[BOJ] 11004 : K번째 수
11004 : K번째 수 풀이 원래는 퀵소트를 응용한 퀵서치(?) 뭐 그런 걸로 짜야한다는데 귀찮아서 레퍼런스를 뒤져보니 엄청난 물건을 찾아냈다 (!!) 코드 #include <iostream> #include <algorithm> using namespace std; int n, k, a[5000005]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; nth_element(a, a + k - 1, a + n); cout << a[k - 1]; return 0; } 아무말 백준, 백준 온라인 저지,...