-
[BOJ] 10801 : 카드게임
10801 : 카드게임 풀이 단순 구현. 코드 #include <bits/stdc++.h> using namespace std; int a[20], x, y; int main() { for (int i = 0; i < 20; i++) scanf("%d", &a[i]); for (int i = 0; i < 10; i++) { if (a[i] > a[i + 10]) x++; if (a[i] < a[i + 10]) y++; } if (x > y) puts("A"); else if (x < y) puts("B"); else puts("D"); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 12911 : 좋아하는 배열
12911 : 좋아하는 배열 풀이 dp[i][j] = 길이가 i이고, 첫번째 숫자가 j 나머지 연산에 주의하자. 코드 #include <stdio.h> typedef long long ll; const int mod = 1000000007; int N, K; int dp[11][100001]; ll sum[11]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i <= K; ++i) dp[1][i] = 1; sum[1] = K; for (int i = 2; i <= N; ++i) { sum[i - 1] += mod; for (int j =...
-
[BOJ] 12869 : 뮤탈리스크
12869 : 뮤탈리스크 풀이 음 원래 dp로 풀려고 했는데 그냥 bfs로 풀었다. dp[i][j][k] = 1번, 2번, 3번 scv의 체력으로 두고 풀어도 된다. 코드 #include <bits/stdc++.h> using namespace std; int N, A[3], ans = 987654321; const int D[6][3] = { {1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1} }; bool chk[61][61][61][20]; struct ABC { int a, b, c, x; ABC() {} ABC(int a, int b, int c, int x) : a(a), b(b), c(c), x(x) {} }; int main() { scanf("%d", &N); for (int...
-
[BOJ] 2661 : 좋은 수열
2661 : 좋은 수열 풀이 재귀로 작은 숫자부터 들어가면서 문자를 비교해주자 코드 #include <bits/stdc++.h> using namespace std; int n, a[88]; void gogo(int cnt) { for (int i = 1; i <= cnt / 2; i++) { if (equal(a + cnt - i, a + cnt, a + cnt - i - i)) return; } if (cnt == n) { for (int i = 0; i < n; i++) printf("%d", a[i]); exit(0); } for (int i...
-
[BOJ] 3683 : 고양이와 개
3683 : 고양이와 개 풀이 이분그래프에서의 Maximum Independent Set(최대 독립 집합)을 구하는 문제이다. size(maximum independent set) + size(maximum matching) = size(vertices) 이거를 기억하자. 문제를 그래프화 시켜보자. 시청자를 노드, 의견 충돌을 엣지라고 두자. 시청자들은 cat을 남기고 dog를 떨어트리거나, dog를 남기고 cat을 떨어트리는 집단으로 나눌 수 있다. 그렇게 나눠서 엣지를 연결하면 이분그래프가 된다! 그런데 maximum independent set을 구하긴 힘드니까 위의 식을 정리해서, size(vertices) - size(maximum matching)를 구하자! 결국 이분매칭 문제가 되었다. 코드 #include <bits/stdc++.h> using namespace std;...
-
[BOJ] 1605 : 반복 부분문자열
1605 : 반복 부분문자열 풀이 suffix array practice 코드 #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; int n, ans; int suf[MAXN], rev[MAXN]; char str[MAXN]; void cntsort(vector<int>& ord, int m) { int i; vector<int> cnt(m + 1, 0), tmp(n + 1); for (i = 0; i < n; i++) cnt[ord[i]]++; for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1]; for (i = n; i--;) tmp[--cnt[ord[suf[i]]]] = suf[i];...
-
[BOJ] 12904 : A와 B
12904번: A와 B 풀이 직접 시뮬레이션 해보면 된다! 코드 #include <bits/stdc++.h> using namespace std; string S, T; void reverse(string K) { for (int i = 0; i < K.length(); ++i) T[K.length() - i - 1] = K[i]; } int main() { cin >> S >> T; int flag = 0; while (true) { if (S.length() == T.length()) { if (!S.compare(T)) flag = 1; break; } int len = T.length() - 1; char now = T[len];...
-
[BOJ] 12946 : 육각 보드
12946 : 육각보드 풀이 잘 생각해보면 보드는 최대 3개의 색으로 칠할 수 있다. 여기를 참고. 0과 1인 경우는 따로 처리해주고 DFS로 돌면서 이분그래프이면 답은 2, 아니면 3이다. 코드 #include <bits/stdc++.h> using namespace std; const int dx[6] = { -1,-1,0,0,1,1 }; const int dy[6] = { 0,1,-1,1,-1,0 }; int n, ans, col[51][51]; char e[51][51]; void dfs(int x, int y, int c) { col[x][y] = c; ans = max(ans, 1); for (int i = 0; i <...
-
[BOJ] 13305 : 주유소
13305 : 주유소 풀이 지금 주유소보다 더 작은 주유소가 나올 때 까지 누적하며 풀면 된다. 그리디! 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 1e5 + 10; int n, i, val, dst[n_], prv = 1e9 + 10; long long ans; int main() { scanf("%d", &n); for (i = 0; i < n - 1; i++) scanf("%d", &dst[i]); for (i = 0; i < n - 1; i++) { scanf("%d", &val); prv = min(prv,...
-
[BOJ] 2531 : 회전 초밥
2531 : 회전 초밥 풀이 범위를 나타내는 left와 right를 두고 inch worm으로 계산해나가면 된다. 근데 그냥 반복문으로도 풀 수 있다. 코드 #include <stdio.h> #include <algorithm> using namespace std; int N, D, K, C; int sushi[30000 + 3000 + 3]; int cur_cnt[3000 + 3], cur_ans; void push(int sushi_num) { if (!cur_cnt[sushi_num]) ++cur_ans; ++cur_cnt[sushi_num]; } void pop(int sushi_num) { --cur_cnt[sushi_num]; if (!cur_cnt[sushi_num]) --cur_ans; } int main() { scanf("%d %d %d %d", &N, &D, &K, &C); for (int...