-
[BOJ] 15368 : Birokracija
15368 : Birokracija 풀이 트리에 존재하는 모든 노드에 대해, 각각의 노드에서 루트까지의 거리를 더하는 문제이다. 음… 그냥 짜면 된다. 코드 #include <cstdio> int n, par[200002], cnt[200002]; long long ans[200002]; int main() { scanf("%d", &n); for (int i = 2; i <= n; i++) scanf("%d", &par[i]); for (int i = n; i >= 1; i--) { ans[par[i]] += ++ans[i] + ++cnt[i]; cnt[par[i]] += cnt[i]; } for (int i = 1; i <= n; i++) printf("%lld ",...
-
[BOJ] 15367 : Spirale
15367 : Spirale 풀이 달.팽.이.조.아.!.! 코드 #include <cstdio> #include <algorithm> const int dx[2][4] = { {0,-1,0,1},{0,-1,0,1} }; const int dy[2][4] = { {-1,0,1,0},{1,0,-1,0} }; int n, m, k; int a[500][500]; int main() { scanf("%d %d %d", &n, &m, &k); while (k--) { int x, y, c, num = 1, cnt = 2, dir = 0; scanf("%d %d %d", &x, &y, &c); x += 249, y += 249; if (!a[x][y]) a[x][y] = 1; while (dir <...
-
[BOJ] 15366 : Olivander
15366 : Olivander 풀이 정.렬.조.아 코드 #include <cstdio> #include <algorithm> using namespace std; int n, a[100], b[100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) scanf("%d", &b[i]); sort(a, a + n); sort(b, b + n); while (n--) if (a[n] > b[n]) return !printf("NE"); return !printf("DA"); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨,...
-
[BOJ] 15998 : 카카오머니
15998 : 카카오머니 풀이 주어지는 입력을 a[i], b[i]라고 하자. b[i]-b[i-1] == a[i]인 경우는 돈을 뽑아서 쓰지 않는 정상적인(?) 경우이다. b[i]-b[i-1] != a[i]인 경우는 비정상적인(?) 경우이다. 여기서 비정상적인(?) 경우도 두 경우로 나뉜다. 하나는 인출하지 않는 상황에서 남은 금액이 맞지 않는 경우, 이건 그냥 짜주자. 인출하는 경우에, 은행에서 인출하는 금액 k는 b[i]-b[i-1]-a[i]이다. 오 그렇다면 이러한 k가 여러개 있을 수 있는데, 우리가 구하는 건 공통된 k이므로 이러한 k들의 gcd를 구해주자. 그러한 gcd 값을 gcd_k라고 하자. 그럼 답이 모순되는...
-
[BOJ] 4256 : 트리
4256 : 트리 풀이 어찌저찌 트리 다시 만들고 잘 짜면 된다. 풀이가 너무 부실한데? 다음의 예제를 보자. 8 3 6 5 4 8 7 1 2 5 6 8 4 3 1 2 7 예를 들어, 지금 inorder로 3을 보고 있다면 preorder 기준으로 3을 반으로 나누면 5 6 8 4, 1 2 7이 있다. 이 말은 노드3에 대해, 5 6 8 4는 왼쪽, 1 2 7은 오른쪽 서브트리 노드들이라는 뜻이다. 이제 이를 토대로 쭉 짜보자....
-
[BOJ] 3758 : KCPC
3758 : KCPC 풀이 주어진 조건대로 정렬해서 구현하면 된다. 코드 #include <bits/stdc++.h> using namespace std; struct abc { int sco, sub, tim, idx; bool operator <(abc a)const { if (sco == a.sco) { if (sub == a.sub) { return tim < a.tim; } return sub < a.sub; } return sco > a.sco; } }; int main() { int tc; scanf("%d", &tc); while (tc--) { int n, k, t, m; abc a[103][103]; memset(a, 0, sizeof(a)); scanf("%d...
-
[BOJ] 7662 : 이중 우선순위 큐
7662 : 이중 우선순위 큐 풀이 multiset을 써서 풀었는데 map으로 풀어도 될 거 같고 아무튼 그냥 짜면 된다. 코드 #include <iostream> #include <set> using namespace std; int main() { int t; cin >> t; while (t--) { int k; cin >> k; char c; int n; multiset<int> v; while (k--) { cin >> c >> n; if (c == 'I') { v.insert(n); } else if (c == 'D' && v.size() > 0) { if (n...
-
[BOJ] 4243 : 보안 업체
4243 : 보안 업체 풀이 내가 지금 [left, right] 구간을 방문한 상태라고 하면, 다음 상태는 [left-1, right] 또는 [left, right+1]가 될 것이다. 이를 토대로 다이나믹 프로그래밍을 해주자. 단, 다음 두 상태로 나아갈 때 left에 서있는지 right에 서있는지에 따라 거리합이 달라지므로 이를 유의해서 코드를 짜보자. 코드 #include <cstdio> #include <cstring> typedef long long ll; int tc, n, s, a[102]; ll dp[2][102][102]; ll min(ll a, ll b) { return a<b?a:b; } ll dst(int x, int y) {...
-
[BOJ] 1713 : 후보 추천하기
1713 : 후보 추천하기 풀이 짜라는대로 짜면 된다. 코드 #include <cstdio> #include <deque> #include <algorithm> using namespace std; int n, m; struct abc { int idx, vote, time; bool operator <(abc a)const { if (vote == a.vote) return time < a.time; return vote < a.vote; } }; int main() { deque<abc> d; scanf("%d %d", &m, &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); for (abc &it : d)...
-
[BOJ] 16120 : PPAP
16120 : PPAP 풀이 일반적인 괄호 문자열 문제랑 비슷하게 해결하면 된다. 코드 #include <cstdio> int t; char a[1000003], s[1000003]; int ppap() { if (t < 4) return 0; if (s[t-4]=='P'&&s[t-3]=='P'&&s[t-2]=='A'&&s[t-1]=='P') return 1; return 0; } int main() { scanf("%s", a); int cnt = 0; for (int i = 0; a[i]; i++) { s[t++] = a[i]; while (ppap()) t -= 4, s[t++] = 'P'; } puts(t == 1 && s[0] == 'P' ? "PPAP" : "NP");...