-
[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]의 최댓값이...
-
[BOJ] 1413 : 박스 안의 열쇠
1413 : 박스 안의 열쇠 풀이 모든 열쇠를 얻으러면, 열쇠들 사이에 사이클이 생겨야한다. 우리에겐 k개의 폭탄이 있기 때문에, 이 열쇠들을 k개의 집합으로 나눠서 사이클을 만드는 경우의 수를 세면 된다. n개의 원소를 k개의 원순열로 분할하기 위해, 제1종 스털링 수라는 걸 사용해보자. s(n, k) = s(n-1, k-1) + (n-1)*s(n-1, k)라는 점화식이 나온다. gcd로 최대공약수를 구하고, 합으로 나눠주면 끝! 코드 #include <stdio.h> typedef long long ll; int n, m, i, j; ll dp[21][21] = { 1 }, div;...
-
[BOJ] 1412 : 일방통행
1412 : 일방통행 풀이 단방향과 양방향 간선이 섞여있는 그래프가 주어진다. 양방향 간선들을 모두 단방향 간선으로 바꾸었을 때, 사이클이 있는지 찾는 문제이다. 일단 솔루션부터 이야기하면, 양방향 간선들은 제껴두고 단방향 간선들만으로 사이클을 이루는지 검사하면 된다. 증명은 음… 증명이라고 하긴 뭐하지만 1->2, 1->3, 2->4, 3->4, 1-4, 2-3의 그래프를 가정하자. 단방향 간선들로 위상정렬을 하면, 1 2 3 4가 나올 것이다. 그리고 1-4와 2-3은 위상정렬 순서에 따라 단방향 간선으로 바꾸어주면 된다. (1->4, 2->3) 코드 #include <stdio.h> int n, vst[101], flag;...
-
[BOJ] 2667 : 단지번호붙이기
2667 : 단지번호붙이기 풀이 dfs를 돌려보자! 맵을 한 바퀴 쭉 돌면서, 아직 탐색하지 않은 단지를 만나면 dfs를 돌리자! 새로운 단지를 만날 때마다 단지 번호도 하나씩 늘려주자! 코드 #include <cstdio> #include <algorithm> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, k, cnt[26 * 26]; char arr[26][26]; void dfs(int x, int y) { arr[x][y] = '0', cnt[k]++; for (int i = 0; i < 4; i++) { int nx...
-
[BOJ] 11779 : 최소비용 구하기 2
11779 : 최소비용 구하기 2 풀이 다익스트라를 쓰면 된다! 대신 trace(=trc)배열을 만들어서 노드 i가 어디서 왔는지 저장해주고, 나중에 역으로 따라서 출력하면 된다. 코드 #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; const int n_ = 1e3 + 3; const int INF = 1e9; struct edg { int idx, dst; edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int n, m, trc[n_],...