-
[BOJ] 2688 : 줄어들지 않아
2688 : 줄어들지 않아 풀이 보이지 않아~~ 코드 #include <cstdio> int tc, n; long long sum, d[66][10]; int main() { for (int i = 0; i <= 9; i++) { d[1][i] = 1; } for (int i = 2; i <= 64; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= j; k++) { d[i][j] += d[i-1][k]; } } } for (scanf("%d", &tc); tc--;) {...
-
[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] 15267 : Justified Jungle
15267 : Justified Jungle 풀이 트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다. 즉, 노드는 n의 약수로만 나눠질 수 있다. 100만 이하 자연수의 약수 개수가 최대 240개니까 O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠… 아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다. 트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자. 음… 그냥 코드를 보는 게 더 빠르겠다. 코드 #include <cstdio> #include <vector> using namespace std; int n,...
-
[BOJ] 15264 : Gambling Guide
15264 : Gambling Guide 풀이 1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다! 그러니까 N에서부터 1로, 거꾸로 가면서 구해주자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int n_ = 3e5+3; int n, m, sdeg[n_]; double dp[n_], sdp[n_]; struct abc { int idx; double val; bool operator <(abc a)const { return val > a.val; } }; priority_queue<abc> pq; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for...
-
[BOJ] 14961 : Untangling Chain
14961 : Untangling Chain 풀이 가장 위, 가장 아래, 가장 오른쪽, 가장 왼쪽의 좌표를 기억해두자. 그리고 항상 그 좌표보다 한칸 더 위로 직선을 쏴주자. 혹은 내 코드처럼 같은 방향(시계, 반시계)으로 두 번 이상 전진하는 경우로 접근해도 된다. 코드 #include <cstdio> int n, i, now, prv; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) { printf("%d ", now-prv ? 1 : i); prv = now; scanf("%d %d", &now, &now); } return...
-
[BOJ] 4801 : Nine
4801 : Nine 풀이 짜라는대로 짜면 된다 약간 영어 독해 문제 코드 #include <cstdio> #include <algorithm> using namespace std; inline int calc(int n) { int r = 0; while (n) { r += n%10==9; n /= 10; } return r; } int main() { int h, m; while (scanf("%d:%d", &h, &m) && (h || m)) { int a = h*60+m; int rcnt = -1, rerr = 1e9, ri = -1, rj = -1; for (int...
-
[BOJ] 3747 : 완벽한 선거!
3747 : 완벽한 선거! 풀이 MAKE WOOKJE GREAT AGAIN!! 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 1000*2+2; int n, m, cnt, scc[n_], chk[n_], ans[n_]; vi gph[n_]; vector<vi> res; stack<int> stk; int getSCC(int now) { chk[now] = ++cnt; int ret = chk[now]; stk.push(now); for (int nxt : gph[now]) { if (!chk[nxt]) ret = min(ret, getSCC(nxt)); else if (!scc[nxt]) ret = min(ret, chk[nxt]); } if...
-
[BOJ] 3648 : 아이돌
3648 : 아이돌 풀이 사랑도 그러게 별 수 없나봐 언제 그랬냐는 듯 계절처럼 변해가 그리워져 미치도록 사랑한 그날들이 내 잃어버린 날들이 참 많이 웃고 울었던 그때 그 시절의 우리 네가 떠올라 밤새 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 1000*2+2; int n, m, cnt, scc[n_], chk[n_], ans[n_]; vi gph[n_]; vector<vi> res; stack<int> stk; int getSCC(int now) { chk[now] = ++cnt; int ret =...
-
[BOJ] 4485 : 녹색 옷 입은 애가 젤다지?
4485 : 녹색 옷 입은 애가 젤다지? 풀이 lulu lala 코드 #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, t, x, a[133][133], d[133][133]; struct abc { int x, y, c; bool operator <(abc a)const { return c > a.c; } }; int main() { for (scanf("%d", &n); n; scanf("%d", &n)) { for (int i = 1; i <=...
-
[BOJ] 7469 : K번째 숫자
7469 : K번째 숫자 풀이 구간합 트리를 쫌 변형해보자. 구간합 트리는 [lft, rgt] 구간에 있는 원소들의 합을 관리한다. 여기서! 원소들의 합을 원소들로 바꿔서 관리해주자! 노드를 int: 구간합이 아니라 vector: 구간의 원소들로 관리하는 거다. 구간을 실체화 시켰다고 하면 될라나? 노드가 2*n개이므로 메모리는 O(n log n)으로 충분하다! 이제 각각의 벡터에는 [lft, rgt] 구간의 원소들이 들어있게 되었고, 이제 각각의 벡터를 정렬해주자. 그리고 쿼리가 들어오면, [s, e] 구간에서 x번째 수가 무엇인지 찾아낼 것이다. 그 수를 이분탐색으로 찾아줄 건데 이건...
-
[BOJ] 14971 : A Garden With Ponds
14971 : A Garden With Ponds 풀이 코드 개더러워… 코드 #include <cstdio> #include <algorithm> #define REP(k,l,r) for(int k=(l);k<(r);k++) using namespace std; int n, m, a[12][12]; int main() { while (1) { scanf("%d %d", &n ,&m); if (!n && !m) return 0; REP(i,1,n+1) REP(j,1,m+1) scanf("%d", &a[i][j]); int res = 0; REP(i,1,n+1) REP(j,1,m+1) { REP(x,i+2,n+1) REP(y,j+2,m+1) { int mo = 1e9; REP(k,i,x+1) mo = min(mo, min(a[k][j], a[k][y])); REP(k,j,y+1) mo = min(mo, min(a[i][k], a[x][k])); int mi = -1,...
-
[BOJ] 14969 : Taro`s Shopping
14969 : Taro’s Shopping 풀이 별빛이 내린다 코드 #include <cstdio> int n, m, a[1001]; int main() { while (1) { scanf("%d %d", &n, &m); if (!n && !m) { return 0; } for (int i = 0; i < n; i++) { scanf("%d", a + i); } int res = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j)...
-
[BOJ] 10531 : Golf Bot
10531 : Golf Bot 풀이 골프 봇이 칠 수 있는 거리를 체킹 배열 a와 b에 체크했다고 생각하자. 두 배열을 bool 곱셈한 배열을 c배열이라고 하자. 만약 a[i] != 0 && b[j] != 0라면 c[i+j] != 0도 성립한다. 코드 #define _USE_MATH_DEFINES #include <cstdio> #include <cmath> #include <complex> #include <vector> #include <algorithm> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef complex<double> base; void fft(vector<base> &a, bool invert) { int n = sz(a); for (int i=1,j=0;i<n;i++){ int...
-
[BOJ] 10265 : MT
10265 : MT 풀이 , 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; using vi = vector<int>; const int n_ = 1e3 + 1; int n, k; int a[n_], vst[n_], cyc[n_], scc[n_], dph[n_], dp[n_]; vector<int> b[n_]; int c_dfs(int now, int dep, int num) { vst[now] = num, dph[now] = dep; if (vst[a[now]] == num) return dph[now] - dph[a[now]] + 1; return c_dfs(a[now], dep + 1, num); } int s_dfs(int now, int num) {...
-
[BOJ] 2698 : 인접한 비트의 개수
2698 : 인접한 비트의 개수 풀이 그리워하면 언젠가 만나게 되는 코드 #include <stdio.h> int q, n, k, d[111][111][2]; int main() { d[1][0][0] = d[1][0][1] = 1; for (n = 2; n <= 100; n++) for (k = 0; k < n; k++) d[n][k][0] = d[n-1][k][0] + d[n-1][k][1], d[n][k][1] = d[n-1][k][0] + (k ? d[n-1][k-1][1] : 0); for (scanf("%d", &q); q--;) scanf("%d %d", &n, &k), printf("%d\n", d[n][k][0] + d[n][k][1]); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 9084 : 동전
9084 : 동전 풀이 그리워하면 언젠가 만나게 되는 코드 #include <stdio.h> #include <string.h> int main() { int T, N, M, p, i, j, n[21], d[10001]; scanf("%d", &T); while (T--) { scanf("%d", &N); memset(n, 0, sizeof(n)); memset(d, 0, sizeof(d)); for (i = 1; i <= N; i++) scanf("%d", &n[i]); scanf("%d", &M); d[0] = 1; for (i = 1; i <= N; i++) for (j = 0; j <= M - n[i]; j++) d[j + n[i]] +=...
-
[BOJ] 10251 : 운전 면허 시험
10251 : 운전 면허 시험 풀이 dp[i][j][k][d] = (i, j)까지 방향을 k번 틀고 d방향에서 왔을 때의 최소 연료량 아 졸리다 자세한 풀이는 다른 블로그를 보는 게 더 좋겠다! 코드 #include <stdio.h> #include <string.h> int min(int a, int b) { return a < b ? a : b; } int n, m, l, g, dp[102][102][102][2], gas[102][102][2]; int main() { int T; for (scanf("%d", &T); T; T--) { scanf("%d %d %d %d", &n, &m, &l, &g); for...
-
[BOJ] 10252 : 그리드 그래프
10252 : 그리드 그래프 풀이 항상 사이클을 만들 수 있다. 첫 번째 행을 제외하고 ㄹ 모양으로 돌다가 마지막에 첫 번재 행으로 돌아와서 올라가주면 된다. 코드 #include <stdio.h> int main() { int tc; for (scanf("%d", &tc); tc; tc--) { int n, m, i, j; scanf("%d %d", &n, &m); puts("1"); for (i = 0; i < m; i++) printf("(%d,%d)\n", 0, i); for (i = 1; i < n; i++) { if (i % 2) for (j =...
-
[BOJ] 2231 : 분해합
2231 : 분해합 풀이 각 자리수의 최대값이 9이므로 [n-9*자릿수, n] 구간만 조사해도 된다! 코드 #include <stdio.h> int n, i, j, cnt, sum; int main() { scanf("%d", &n); i = n; while (i) i /= 10, cnt++; for (i = n - 9 * cnt; i < n; i++) { sum = i; for (j = i; j; j /= 10) sum += j % 10; if (sum == n) break; } printf("%d", i != n...
-
[BOJ] 10250 : ACM 호텔
10250 : ACM 호텔 풀이 규칙을 잘 찾아보자! 코드 #include <stdio.h> int main() { int t, h, w, n; scanf("%d", &t); while(t--) { scanf("%d %d %d", &h, &w, &n); n--; printf("%d%02d\n", n%h+1, n/h+1); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 4586 : Image Compression
4586 : Image Compression 풀이 흑흑 문제를 잘못 읽어서 한 번 틀렸다 ㅠㅠ 네 조각씩 나눠서 분할정복을 하면 된다. 제한이 크지 않으므로 나이브하게 사각형을 다 돌아보면 된다. 룰루 코드 #include <stdio.h> #define y1 fuck typedef double db; int n, t; char a[66][66]; void go(int x1, int y1, int x2, int y2) { if (x1 == x2 && y1 == y2) return; int siz = (x2 - x1 + 1) * (y2 - y1 + 1),...