-
[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...