-
[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...
-
[BOJ] 1411 : 비슷한 단어
1411 : 비슷한 단어 풀이 뭔가 번역이 좀 애매한 것 같은데 a->b면 b->a도 당연히 성립할 줄 알았더니 a->b만 성립하면 되는 문제였다 (…) 단순 구현 문제이다. 코드 #include <iostream> #include <string> using namespace std; int n, i, j, k, ans; string str[101]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) cin >> str[i]; for (i = 0; i < n - 1; i++) for (j = i + 1; j <...
-
[BOJ] 9466 : 텀 프로젝트
9466 : 텀 프로젝트E 풀이 위상정렬을 하자! 코드 #include <stdio.h> #include <memory.h> const int n_ = 100000 + 1; int ans, a[n_], idg[n_]; bool chk[n_]; void dfs(int n) { chk[n] = true; ++ans, --idg[a[n]]; if (!chk[a[n]] && !idg[a[n]]) dfs(a[n]); } int main() { int t, n, i, j; scanf("%d", &t); for (i = 1; i <= t; ++i) { ans = 0; scanf("%d", &n); memset(chk, 0, sizeof(chk)); memset(idg, 0, sizeof(idg)); for (j = 1; j...
-
[BOJ] 13023 : ABCDE
13023 : ABCDE 풀이 A-B-C-D-E 관계의 5명이 있는지 구하는 문제였다. dfs를 돌려주자. 코드 #include <stdio.h> #include <memory.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 2000 + 1; bool ans, chk[n_]; int n, m; vector<int> v[n_]; void dfs(int now, int cnt) { if (cnt == 5) { ans = true; return; } chk[now] = true; for (int next : v[now]) { if (!chk[next]) dfs(next, cnt + 1); if (ans) return; } chk[now]...
-
[BOJ] 1427 : 소트인사이드
1427 : 소트인사이드 풀이 단순 구현 코드 #include <bits/stdc++.h> using namespace std; int i, cnt[10]; string str; int main() { cin >> str; for (i = 0; i < str.length(); i++) cnt[str[i] - '0']++; for (i = 9; i >= 0; i--) while (cnt[i]--) printf("%d", i); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11057 : 오르막 수
11057 : 오르막 수 풀이 점화식을 세우자! dp[수열의 자릿수 i][i번째 자릿수의 숫자 j] 일 때의 경우의 수 dp[i][j] = dp[i-1][j] + dp[i][j-1] 코드 #include <stdio.h> const int mod = 10007; int n, i, j, ans, dp[10001][10]; int main() { scanf("%d", &n); for (i = 0; i <= 9; i++) dp[1][i] = 1; for (i = 2; i <= n; i++) { dp[i][0] = dp[i - 1][0]; for (j = 1; j <= 9; j++) {...
-
[BOJ] 7576 : 토마토
7576 : 토마토 풀이 bfs를 돌리자 코드 #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, a[1003][1003]; queue<pair<int, int> > que; int main() { scanf("%d %d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); if (a[i][j] == 1) que.push({ i,j }); }...
-
[BOJ] 4195 : 친구 네트워크
4195 : 친구 네트워크 풀이 새로운 친구들이 추가될 때 마다 merge를 해주자! 모든 노드에 대해 해당 원소가 속한 네트워크의 크기를 미리 구해두고 merge 할 때 합쳐주자! 이 문제에서는 map을 쓰면 편하게 구현할 수 있다. unordered_map을 사용하면 map보다 빠르게 구현할 수 있다. 자세한 건 cpp 레퍼런스를 참고하자. 코드 #include <iostream> #include <unordered_map> #include <string> #include <algorithm> using namespace std; const int n_ = 1e5 + 1; int pnt[n_ * 2], cnt[n_ * 2]; int find(int u)...
-
[BOJ] 2150 : Strongly Connected Component
2150 : Strongly Connected Component 풀이 scc를 구현하자! 다른 블로그에 좋은 scc 설명이 많으니까 나는 구현만 해야겠다 원래 stl stack 써서 짰는데 메모리 많이 먹길래 기분 나빠서(?) 배열로 바꿨다. 처음 코드가 타잔, 다음 코드가 코사라주이다. 코드 타잔 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vi; const int v_ = 1e4 + 1; int v, e, cnt, pos, scc[v_], chk[v_], stk[v_]; vi gph[v_]; vector<vi> res; int dfs(int now) { chk[now] = ++cnt;...
-
[BOJ] 11048 : 이동하기
11048 : 이동하기 풀이 간단하게 점화식을 세우면 dp[i][j] = dp[i][j] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])라는 식이 나온다. 다시 생각해보자. dp[i+1][j+1]을 굳이 갈 필요가 없다. 사탕의 개수가 음수가 아니기 때문에, dp[i+1][j] 또는 dp[i][j+1]을 거쳐서 dp[i+1][j+1]에 가는 값이 dp[i+1][j+1]로 바로 가는 값 보다 작아질 수 없다. 쉽게 말하자면 가로+세로(세로+가로)로 가는 값이 대각선으로 가는 값 보다 작아질 일이 없다는 것이다. 더 나가아서, dp 배열을 1차원으로 줄일 수 있다. 입력을 왼쪽위->오른쪽아래으로 받으면서 진행하게 되면 dp[j-1]은 dp[i][j-1]의 최댓값, dp[j]는 dp[i-1][j]의 최댓값이...