-
[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]의 최댓값이...