-
[BOJ] 2492: 보석
2492: 보석 풀이 이 풀이를 참고하자. 복붙 날먹 꺼-억 아 이 문제는 사각형이 격자를 벗어나면 안 되니까 주의하자. 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, k; int dap, dap_x, dap_y; struct abc { int x, y; } a[111]; void go(int x, int y) { int cnt = 0; for (int i = 1; i <= t; i++) { if (x <= a[i].x && a[i].x <= x+k && y <= a[i].y && a[i].y...
-
[BOJ] 2496: 금강석
2496: 금강석 풀이 (x, y)의 좌표계를 변환하자. (x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다. 좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다. T가 100밖에 안 된다는 점을 주목하자. 정답에 포함되는 어떤 금강석들의 집합이 있다고 하자. 이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다. 정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자. 항상 두 개의 금강석이 왼쪽과 위쪽 변에...
-
[BOJ] 10759: 팰린드롬 경로3
10759: 팰린드롬 경로3 풀이 d[i][j] = 문자열의 길이가 k이고, i행에서 시작해서 j행으로 끝나고, 그 문자열의 중심이 배열의 대각선(왼쪽 아래~오른쪽 위)에 있을 때, 그 문자열이 팰린드롬인 경우의 수 d[k][i][j] = d[k-2][i][j]+d[k-2][i+1][j]+d[k-2][i][j-1]+d[k-2][i+1][j-1] 식은 위와 같고, 배열은 k를 토글링 해서 n^2개만 사용할 것이다. (1,1)~(n,n)의 문자열은 길이가 항상 홀수이다. 중앙의 diagonal 대각선을 기준으로, 팰린드롬의 길이를 앞뒤로 2씩 확장해 나갈 수 있다. (a,b)~(c,d)의 중심이 대각선에 겹치려면, (a-1)+(b-1) = |(c-n)+(b-n)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.) a와...
-
[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...
-
[BOJ] 10167: 금광
10167: 금광 풀이 이 문제와 비슷하게 분할정복으로 접근한다. x축을 기준으로 정렬해서, 모든 [l, r] 구간에서 최댓값을 하나씩 찾을 것이다. 시작점을 하나 정해놓고, 끝점까지 스위핑 하면서 최댓값을 찾아 주자. 스위핑이 하나 전진할 때마다 분할정복 트리를 업데이트 해 주면 된다. 이러한 구간이 많아야 3000^2개이므로 여기에 로그 붙여도 충분하다. 세그트리 업데이트 하는 느낌으로 분할정복을 하면 된다. 나는 멍청하게 구간합 업데이트를 펜윅트리 써서 했는데 여러분들은 그러지 말자. ㅋㅋㅋㅋ 까다로운 반례가 있으므로 주의하자. 코드 #include <cstdio> #include <algorithm> #include <vector>...
-
[BOJ] 16993 : 연속합과 쿼리
16993: 연속합과 쿼리 풀이 분할정복 하는 느낌, 혹은 세그트리 짜는 느낌으로 접근하면 된다. 노드 하나에 3개의 값이 들어가는데, mmax(s, e) = 가운데를 지나는 구간의 최대 합 lmax(s, e) = s를 포함하는 구간의 최대 합 rmax(s, e) = e를 포함하는 구간의 최대 합 위의 것들을 분할정복 하듯이 전처리해서 들고 있는다. 그리고 재귀 세그트리 짜듯이 쿼리를 날리면 쿼리 당 O(log N)에 답을 계산할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll...
-
[BOJ] 9240 : 로버트 후드
9240 : 로버트 후드 풀이 로테이팅 캘리퍼스 코드 #include<cstdio> #include<algorithm> #include<tuple> #include<vector> #include<cmath> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct POINT{ int x, y; bool operator <(POINT a)const { return x == a.x ? y < a.y : x < a.x; } POINT operator -(POINT a)const { return { x-a.x,y-a.y }; } }; int N; ll sq(int x){ return (ll)x*x; } ll dst(POINT A, POINT B) { return sq(A.x-B.x)+sq(A.y-B.y); } int...
-
[BOJ] 1062 : 가르침
1062 : 가르침 풀이 그냥 완전탐색하면 된다 근데 그냥 하면 시간 초과가 난다 앞뒤에 anta tica를 제거하고 잘 돌려야 한다 코드 #include <bits/stdc++.h> using namespace std; int n, k, dap, a[55]; char s[55]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; s[j]; j++) a[i] |= (1<<(s[j]-'a')); } int x = (1<<0)|(1<<2)|(1<<8)|(1<<13)|(1<<19); for (int i = x; i < (1<<26);...
-
[BOJ] 2162 : 선분 그룹
2162 : 선분 그룹 풀이 선분이 교차하면 묶어주면 된다 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; typedef pair<int, int> pi; int n, par[3003], cnt[3003]; pi p[6003]; int ccw(pi a, pi b, pi c) { int r = a.fst*b.snd + b.fst*c.snd + c.fst*a.snd; r -= a.snd*b.fst + b.snd*c.fst + c.snd*a.fst; if (r > 0) return 1; if (r < 0) return -1; return 0; } int iscross(pi a, pi b, pi...
-
[BOJ] 2152 : 여행 계획 세우기
2152 : 여행 계획 세우기 풀이 주어진 그래프에서 scc를 구해서, 각 컴포넌트를 노드로 하는 새로운 그래프를 만들자 scc로 구성된 그래프는 항상 DAG이다 여기서 위상정렬 같은 느낌으로 dp? 같은 느낌으로 으쌰으쌰 하자 타잔으로 scc를 구하면 위상정렬의 역순으로 컴포넌트를 구하게 된다 아몰랑 코드 #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; const int MAXN = 1e4 + 10; int n, m, s, e; int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN]; vi gph[MAXN]; vector<vi> res; int dfs(int now) {...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 2812 : 크게 만들기
2812 : 크게 만들기 풀이 토막 나며 부서진 나의 여러 기대는 공중에 날려 사라져가고 딱딱한 구름 밑에서 벅찬 무게를 견디며 혼자 그렇게 작아져 갔다 코드 #include <cstdio> int n, k, pos; char s[500005]; int main() { scanf("%d %d %c", &n, &k, &s[0]); pos = 1; for (int i = 1; i < n; i++) { scanf("%c", &s[pos]); while (k && pos && s[pos-1] < s[pos]) { s[pos-1] = s[pos]; s[pos] = 0; k--; pos--; }...
-
[BOJ] 1541 : 잃어버린 괄호
1541 : 잃어버린 괄호 풀이 아무도 얘기하지 않는 몇 해가 쉽게 지나 버리고 휑하니 텅 빈 가슴속으로 눈꽃 송이 내려앉는다 아무리 잠들어도 캄캄한 바람 지날 뿐 어떤 꿈도 만나지 못해 코드 #include <cstdio> int sum, tmp, f, n; char s[55] = {1}; int main() { scanf("%s", s+1); for (int i = 1; s[i-1]; i++) { if ('0' <= s[i] && s[i] <= '9') { n *= 10; n += s[i] - '0'; } else if...
-
[BOJ] 1138 : 한 줄로 서기
1138 : 한 줄로 서기 풀이 사람 마음이 참 생각처럼 되질 않아 쓴웃음에 한 번 더 미련을 삼켜 보곤 해 미워하고 싶은데 그것조차 잘 안 돼 너의 기억은 너무나 찬란해 잠 못 들게 해 코드 #include <cstdio> #include <vector> using namespace std; int n, x, a[12]; vector<int> v; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } v.push_back(n); for (int i = n-1; i >= 1;...
-
[BOJ] 2294 : 동전 2
2294 : 동전 2 풀이 가져가 지독한 그리움 기억 속 널 다시 데러가 난 아무렇지 않은 척 애를 써도 또다시 울컥하고 말아 아직도 난 코드 #include <cstdio> int n, k, t, d[100001]; int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= k; i++) { d[i] = 1e9; } for (int i = 1; i <= n; i++) { scanf("%d", &t); for (int j = t; j <= k; j++) {...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 둠두둠칫 코드 #include <cstdio> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j = 4; j <= i; j += 2) d[i] += d[i - j] * 2; } printf("%d", d[n]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++,...
-
[BOJ] 1149 : RGB거리
1149 : RGB거리 풀이 d[i][0] = max(d[i-1][1], d[i-1][2]) d[i][1] = max(d[i-1][0], d[i-1][2]) d[i][2] = max(d[i-1][0], d[i-1][1]) 코드 #include <bits/stdc++.h> using namespace std; int N, r, g, b, R, G, B; int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d %d", &r, &g, &b); r += min(G, B); g += min(R, B); b += min(R, G); R = r; G = g; B = b; } printf("%d", min(min(R,...
-
[BOJ] 2156 : 포도주 시식
2156 : 포도주 시식 풀이 . 코드 int max(int a, int b) { return a > b ? a : b; } n, a, b, c, A, B, C, w; main() { for (scanf("%d", &n); n--;) { scanf("%d", &w); C = c, B = b, A = a; c = B + w; b = A + w; a = max(max(A, B), C); } printf("%d", max(max(a, b), c)); } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 2437 : 저울
2437 : 저울 풀이 일단 주어진 추들의 무게를 정렬해 보자. 1~w까지의 모든 무게를 만들 수 있다고 가정하자. 1~w를 만들 수 있다면 여기에 무게 k의 추를 추가해서 1~w+k까지의 모든 무게를 만들 수 있다. 하지만 만약 k > w+1이라면 w+을 만들 수 없게 된다. 이제 코드로 옮겨보자. 코드 #include <cstdio> #include <algorithm> int n, a[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } std::sort(a, a+n); int mx...
-
[BOJ] 2618 : 경찰차
2618 : 경찰차 풀이 dp[i][j] = 경찰차1이 i번째 사건, 경찰차2가 j번째 사건의 위치에 있을 때 거리 합의 최소값 일반성을 잃지 않고, max(i, j)까지의 사건들을 모두 처리했다고 하자. 지금 처리할 사건을 k번째라고 하자. (k = max(i,j)+1) dst(i, j)는 i번째 사건과 j번째 사건 사이의 거리를 구하는 함수라고 하자. 경찰차1이 k번째 사건을 처리하려면, dp[k][j] = dp[k-1][j] + dst(k, k-1) 경찰차2가 k번째 사건을 처리하려면, dp[i][k] = dp[i][k-1] + dst(k, k-1) 점화식을 잘 정의했다면 여기까지 어렵지 않게 떠올릴 수 있다....
-
[BOJ] 1344 : 축구
1344 : 축구 풀이 각각의 팀이 골을 넣고 말고 하는 경우의 수는 총 4가지 모두 계산해 주자 코드 #include <cstdio> int p[12] = { 0,1,4,6,8,9,10,12,14,15,16,18 }; double a, b, d[19][19][19]; int main() { scanf("%lf %lf", &a, &b); a /= 100, b /= 100; d[0][0][0] = 1; for (int t = 0; t <= 17; t++) { for (int x = 0; x <= t; x++) { for (int y = 0; y <= t; y++)...
-
[BOJ] 9657 : 돌 게임 3
9657 : 돌 게임 3 풀이 다 찢겨져버린 사이 더 기워봐도 다시 그때로 우리 되돌려 놓을 수 없는 그 얘기 날카롭게 패인 이 상처가 깊어 나을 수 없으니 떠나가요 코드 #include <cstdio> int n, d[1001]; int main() { scanf("%d", &n); d[1] = d[3] = d[4] = 1; for (int i = 5; i <= n; i++) { if (!(d[i-1] && d[i-3] && d[i-4])) { d[i] = 1; } } puts(d[n] ? "SK" : "CY"); return...
-
[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] 10881 : 프로도의 선물 포장
10881 : 프로도의 선물 포장 풀이 경우의 수가 그리 많지 않아 모든 경우를 다 탐색해 보면 된다. 각 3개의 직사각형을 옆으로 눕히는 경우까지 고려하면 6^3즈음의 계산을 해야함을 알 수 있다. 돌려돌려~~ 코드 #include <cstdio> #include <algorithm> using namespace std; int a[6], b[6]; inline int one(int i, int j, int k) { return (a[i]+a[j]+a[k])*max({b[i],b[j],b[k]}); } inline int two(int i, int j, int k) { return max(a[i]+a[j],a[k])*(max(b[i],b[j])+b[k]); } int go() { int ret = 1e9; for (int...
-
[BOJ] 14736 : Coke Challenge
14736 : Coke Challenge 풀이 뭐 어떻게 식을 잘 세워주면 되는데 어… 코드를 보는 게 더 빠를 것 같다. 코드 #include <cstdio> #include <algorithm> int n, k, a, ans = 1e9; int main() { scanf("%d %d %d", &n, &k, &a); for (int i = 0; i < n; i++) { int t, s; scanf("%d %d", &t, &s); ans = std::min(ans, k/a+(k/(a*t)+(k%(a*t)?0:-1))*s); } printf("%d", ans); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 15770 : QueryreuQ
15770 : QueryreuQ 풀이 문자열의 끝 문자가 추가 되거나 삭제 될 때, 매번의 추가/삭제 이후에 모든 부분 팰린드롬의 개수를 빠르게 구해야 한다. 문자가 추가/삭제 된다는 조건과 쿼리 문제라는 생각에 뭔가 어려워 보인다. 문자가 끝에서만 추가되고 삭제되기 때문에, 그냥 fix된 문자열에서 다이나믹으로 팰린드롬 구하는 O(n^2) 알고리즘을 그대로 가져오면 된다. 시간 제한이 1초여서 조금 빡빡한 듯 하지만, 엄밀히 따져보면 10000^2에 나누기 상수가 붙어서 1초 보다 좀 덜 돈다. (그리고 컴파일러 -o2 최적화가 붙으면 간단한 10000^2정도는 1초에 충분히...
-
[BOJ] 15553 : 난로
15553 : 난로 풀이 문제를 조금 다르게 생각해 보자. 일직선 상의 정수 좌표 n개가 주어졌을 때, k개 이하의 구간으로 모든 좌표를 묶어야 한다. 이 때, 구간 길이의 합을 최소로 하여라. 인접한 좌표 사이의 길이를 모두 구해놓고 생각해 보자. 상대적으로 긴 구간을 k개의 구간에 포함시키는 것은 손해이다. k개의 구간을 나눌 수 있다는 말은 구간들 중에서 k개의 길이를 답에 포함시키지 않을 수 있다는 말과 같다. 구간의 길이를 모두 구해 정렬하고 가장 작은 n-k개의 구간을 선택해 주자. 우선순위...
-
[BOJ] 16000 : 섬
16000 : 섬 풀이 문제를 조금 정리해 보자. 모든 섬 v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬 u가 존재하는가? 섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자. 그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자. 모든 섬 노드 v에 대해, 1에서 v로 가기 위해 반드시 거쳐야 하는 섬 노드 u가 존재하는가?...
-
[BOJ] 14502 : 연구소
14502 : 연구소 풀이 삼성스럽다. 구현 문제다. 완전탐색 잘 짜주면 된다. 코드 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, s, a[11][11], chk[11][11]; vector<pair<int, int> > virus; int dfs(int x, int y) { int ret = 1; chk[x][y] = 1; for (int i = 0; i < 4; i++) { int nx = x+dx[i], ny...
-
[BOJ] 2842 : 집배원 한상덕
2842 : 집배원 한상덕 풀이 parametric search로도 풀릴 것 같은데 나는 투포인터로 풀었다. 높이가 될 수 있는 후보는 1000000개이지만 주어지는 그리드의 크기가 50*50이 최대이므로 많아야 2500개 후보가 있을 수 있다. 주어진 높이들을 정렬한 다음, 투포인터로 구간을 잡아 dfs를 돌려주자. 코드 #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1,-1,-1,1,1 }; const int dy[] = { -1,1,0,0,-1,1,-1,1 }; int n, sx, sy, k, b[55][55], chk[55][55]; char a[55][55]; vector<int>...
-
[BOJ] 15997 : 승부 예측
15997 : 승부 예측 풀이 6개 각각의 경기마다 W, D, L 3개의 상태가 있으므로 최종 스코어는 총 3^6개의 경우가 나올 수 있다. 개수가 많지 않으니 완전탐색을 해주자. 마지막에 동률인 경우를 예외처리 하는 게 몹시 화가 나지만 인내심을 가지고 풀어보자. 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; map<string, int> m; struct abc { int x, y; double w, d, l; } a[6]; int s[4]; double r[4]; pair<int, int> t[4]; void go(int...
-
[BOJ] 1023 : 괄호 문자열
1023 : 괄호 문자열 풀이 sgc109님 풀이 보고 구현했어요 괄호 문자열의 개수를 구하는 점화식을 구하고 (1)에서 괄호 ㄴㄴ 문자열의 개수를 구하는 점화식을 구하고 (2)를 역추적 하면 풀 수 있어요 코드 #include <cstdio> #include <cstring> typedef long long ll; const ll inf = 0x3f3f3f3f3f3f3f3f; int n; ll k, dp[55][105][2]; ll go(int now, int sum, int isWrong) { if (now == n) { return isWrong || sum!=50; } ll &ret = dp[now][sum][isWrong]; if (ret != inf) {...
-
[BOJ] 2453 : 부서 배치
2453 : 부서 배치 풀이 어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다. 관계는 항상 그래프로 표현할 수 있다. 이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다. 부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다. 이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다. 여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다. 이제 한 그룹의 사람들을 부서1에 배치할지,...
-
[BOJ] 3114 : 사과와 바나나
3114 : 사과와 바나나 풀이 A는 prefix 누적합, B는 suffix 누적합을 구해주자. 불도저가 [i][j]로 오는 방법은 [i-1][j-1], [i-1][j], [i][j-1] 이 세 가지가 있다. 모든 i, j를 돌면서, 위의 세 가지 경우에 대해 최댓값을 계산해주자. i=1이거나 j=1인 경우의 예외 케이스에 주의하자. 코드 #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; int n, m, i, j, a[1502][1502], b[1502][1502], d[1502][1502]; char s[9]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++)...
-
[BOJ] 16174 : 점프왕 쩰리 (Large)
16174 : 점프왕 쩰리 (Large) 풀이 잘 짜주면 된다. 코드 #include <cstdio> int n, i, j, x, a[66][66] = {1}; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { scanf("%d", &x); if (!a[i][j]) continue; if (i+x < n) a[i+x][j] = 1; if (j+x < n) a[i][j+x] = 1; } puts(a[n-1][n-1] ? "HaruHaru" : "Hing"); return 0; } 아무말 백준, 백준 온라인 저지,...
-
[BOJ] 16173 : 점프왕 쩰리 (Small)
16173 : 점프왕 쩰리 (Small) 풀이 잘 짜주면 된다. 코드 #include <cstdio> int n, i, j, x, a[66][66] = {1}; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { scanf("%d", &x); if (!a[i][j]) continue; if (i+x < n) a[i+x][j] = 1; if (j+x < n) a[i][j+x] = 1; } puts(a[n-1][n-1] ? "HaruHaru" : "Hing"); return 0; } 아무말 백준, 백준 온라인 저지,...
-
[BOJ] 16172 : 나는 친구가 적다 (Large)
16172 : 나는 친구가 적다 (Large) 풀이 kmp 잘 짜주면 된다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j - 1]; if (p[i]...
-
[BOJ] 16171 : 나는 친구가 적다 (Small)
16171 : 나는 친구가 적다 (Small) 풀이 잘 짜주면 된다. 근데 그냥 16172번 복붙했다. 코드 #include <iostream> #include <string> using namespace std; int fail[200022]; string a, t, p; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> a >> p; for (auto it : a) if (it < '0' || it > '9') t.push_back(it); for (int i = 1, j = 0; i < p.length(); ++i) { while (j && p[i] != p[j]) j = fail[j -...
-
[BOJ] 16169 : 수행 시간
16169 : 수행 시간 풀이 위상정렬 acm craft인가 그 문제랑 똑같은 것 같다. (사실 기억 안 남 ㅎ) 잘 짜주면 된다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, dap, l[101], t[101], d[101], r[101]; struct edg { int idx, dst; }; vector<edg> gph[101]; void go(int now) { dap = max(dap, r[now]); for (edg nxt : gph[now]) { r[nxt.idx] = max(r[nxt.idx], r[now] + t[nxt.idx] + nxt.dst); if (!(--d[nxt.idx])) go(nxt.idx); } } int...
-
[BOJ] 16168 : 퍼레이드
16168 : 퍼레이드 풀이 degree 짝수가 어쩌구 저쩌구 해서 풀어도 되는데 그냥 제곱 돌려도 된다. 근데 degree 어쩌구 저쩌구 할 때 유의해야 할 점은 connected graph가 아닐 수도 있어서 유니온파인드 같은 걸 해줘야한다. 잘 짜주면 된다. 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[3003][3003]; vector<int> gph[3003]; void dfs(int now, int num, int cnt) { if (cnt == m) { puts("YES"); exit(0); } for (int nxt : gph[now]) { if...
-
[BOJ] 16167 : A Great Way
16167 : A Great Way 풀이 잘 짜주면 된다. 코드 #include <cstdio> #include <queue> #include <vector> #define fst first #define snd second using namespace std; int n, m; struct abc { int idx, cst; }; vector<abc> gph[101]; pair<int, int> dp[101]; int main() { scanf("%d %d", &n, &m); while (m--) { int a, b, c, d, e; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); if (e > 10) c += ((e-10)*d); gph[a].push_back({ b,c...
-
[BOJ] 16166 : 서울의 지하철
16166 : 서울의 지하철 풀이 잘 짜주면 된다. 비트마스크 썼다. 코드 #include <cstdio> #include <queue> #include <map> using namespace std; int n, en; struct abc { int idx, hosun, cnt; bool operator <(abc a)const { return cnt > a.cnt; } }; map<pair<int, int>, int> cnt; map<int, int> subway; int main() { scanf("%d", &n); for (int i = 1, k; i <= n; i++) { scanf("%d", &k); for (int j = 0, x; j < k;...
-
[BOJ] 16165 : 걸그룹 마스터 준석이
16165 : 걸그룹 마스터 준석이 풀이 잘 짜주면 된다. 코드 #include <iostream> #include <string> #include <map> using namespace std; int n, m, num; string grp, str; map<string, string> mp; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; while (n--) { cin >> grp >> num; while (num--) { cin >> str; mp[grp] = str; mp[str] = grp; } } while (m--) { cin >> str >> num; if (!num) for (auto it :...
-
[BOJ] 8073 : Road Net
8073 : Road Net 풀이 인접행렬이 주어질 때, 다음과 같은 식 AB=AC+CB을 만족하는 경우가 있는지를 판별하면 된다. 음… 짜면 된다. 코드 #include <cstdio> int n, i, j, k, f, a[202][202]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &a[i][j]); for (i = 0; i < n; i++) for (j = i+1; j < n; j++) { f = 0; for (k...
-
[BOJ] 8103 : Rooks
8103 : Rooks 풀이 요약: n*n의 체스판에 n개의 룩을 배치해야 하는데, 어떤 룩도 서로를 잡을 수 없도록 배치해야한다. 그런데 그냥 배치하는 건 아니고, 각각의 룩을 배치할 수 있는 어떤 직사각형의 영역이 n개 주어진다. 각각의 룩은 각각의 영역 내에만 배치될 수 있다. 룩은 가로/세로로만 움직일 수 있다는 사실을 조금 관찰해보면, 답을 구하는 데 있어 가로 좌표와 세로 좌표가 독립적임을 알 수 있다. 즉, 한 축(가로 또는 세로)에 대해 조건에 맞게 배치하는 일을 두 번 해주고, 나중에...
-
[BOJ] 8101 : Rods
8101 : Rods 풀이 요약: 양 끝점이 고정된 길이 L의 선분이 있다. 이 선분의 가운데를 이쁘게 늘려서 길이 L+d의 곡선을 만든다. 그럼 길이 L의 현과 길이 L+d의 호가 만들어진다. 이 때, 현의 중심과 호의 중심까지의 거리 x는 얼마일까? 알고리즘에 수학을 싸서 드셔보세요!! 주어진 호를 예쁘게 연장해서 예쁜 원을 만들어주자. 원의 중심에서 현의 끝점까지 예쁜 반지름 r1, r2도 그어주자. 현을 이등분하는 예쁜 반지름 r3도 그어주자. r3와 r2, r3와 r1 사이의 각을 세타라고 하자. 삼각함수를 이용해서 식을...
-
[BOJ] 8091 : Petrol
8091 : Petrol 풀이 KOI 주유소 문제에 자동차 연로탱크의 capacity가 추가된 버전(?) (사실 주유소 문제가 기억 안 나서 맞는지는 모름) 암튼 비슷하다. 시작점에서 끝점까지의 거리가 100만밖에 되지 않는다는 사실! 아하! 그렇다면 시작점으로부터의 거리를 인덱스로 삼는 배열을 하나 만들 수 있겠군! 오, 그럼 자동차를 한 칸씩 움직이면서 연료 탱크 최대값과 가능한 범위 내의 최소 기름값을 잘 관리하면 풀 수 있겠군!! 음… 근데 문제 분류를 어떻게 해야할지 모르겠군 코드 #include <cstdio> #include <queue> using namespace std; int...
-
[BOJ] 8088 : Airports
8088 : Airports 풀이 n개의 노드에 대해, 각 노드의 degree가 주어진다. 주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다. (불가능한 경우는 주어지지 않는다) 남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자. 이런 작업을 degree가 0이 될 때까지 반복하자. 다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다. 그럼 된다. 증명(?) 주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자. 그래프 G에서 degree가 가장...
-
[BOJ] 8093 : Credibility of Witnesses
8093 : Credibility of Witnesses 풀이 믿는다의 정의는 재귀적인데, 1. A는 A를 믿는다, 입력으로 주어진 쌍에 있는 사람들도 믿는다. 2. A가 B를 믿는다면, A는 B가 믿는 모든 사람들을 믿는다. 믿지 않는다의 정의도 재귀적인데, 1. A는 입력으로 주어진 쌍에 있는 사람들을 믿지 않는다. 2. A가 B를 믿는다면, A는 B가 믿지 않는 모든 사람들을 믿지 않는다. 그래서 모든 A에 대해서, A가 믿으면서 믿지 않는 B가 존재하는지 찾는 문제입니다. - said koosaga dfs를 n번 돌려서 O(n^2) 정도에 풀...
-
[BOJ] 8098 : Lecture Halls Reservation
8098 : Lecture Halls Reservation 풀이 회의실 배정이랑 비슷하게 생겼다. 오… 이거 데이터 생겨먹은 게 끝나는 시간을 기준으로 정렬해주고 싶게 생겼다. 시간의 최대 범위가 3만이므로, 각각의 시간에 대해, 해당 시간까지의 최대 해를 계산해줄 수 있다. 약간 다이나믹스러운 느낌으로 d[time] = max(d[time], d[start]+end-start) 주어진 구간의 양 끝점만 보고 삭 긁어주면 된다. 시간 범위가 3만보다 (엄청) 크다면 세그트리 등등을 이용해서 풀어줄 수 있겠다. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, r, d[30003]; pair<int, int>...
-
[BOJ] 8095 : The Number of N-k-special Sets
8095 : The Number of N-k-special Sets 풀이 1부터 N까지의 정수를 최대 한 번씩 사용하는데, 인접한 숫자를 사용하지 않고, k이상의 정수를 만드는 경우의 수를 구해야한다. 딱 문제가 저는 다이나믹이에요!!!! 라고 소리지르고 있다. 나는 두 가지 방법으로 풀었다. 아 그리고 답이 long long 범위마저 넘어가므로 Big Integer스러운 어떤 방법이나 언어를 잘 골라서 구현해야 한다. 방법1 dp[i][k] = 1~i를 사용해서 k를 만드는 경우의 수 i-1(인접하면 안 되니까 i-1)보다 작은 j들에 대해, dp[j][k-i]를 누적하여 세어주면 어렵지 않게 계산할...
-
[BOJ] 8094 : Canoes
8094 : Canoes 풀이 투포인터(?) 같은 느낌으로 그리디하게 풀어주자. 각 카누들의 용량(?)을 정렬해주자. 정렬 후 배열의 양 끝에는 min, max 값이 들어있으므로 양 사이드에서 가운대로 포인터를 옮기며 매칭할 수 있다면 매칭해주자. 코드 #include <cstdio> #include <algorithm> int n, w, i, j, a[30003]; int main() { scanf("%d %d", &w, &n); for (; j<n; j++) scanf("%d", &a[j]); std::sort(a, a+n); for (j = n-1; j && i<j; j--) if (a[i]+a[j]<=w) i++; printf("%d", n-i); return 0; } 아무말 백준,...
-
[BOJ] 8983 : 사냥꾼
8983 : 사냥꾼 풀이 어떤 동물을 사냥할 수 있는지 판단해야한다. 그러기 위해선 어떤 동물에서 가장 가까운 어떤 사냥대를 찾아야 한다. 동물의 y좌표는 모든 사냥대에 대해 절대적인 반면, x좌표는 사냥대에 대해 상대적이다. 그러므로 동물의 x좌표와 사냥대의 x좌표만 비교해서 O(1) 또는 O(log n)의 시간에 가장 가까운 사냥대를 찾을 수 있다. O(1)은 적당히 반복문을 잘 굴리면 되고 O(log n)은 적당히 이분탐색 같은 걸 사용하면 된다. (안 해봤지만 아마 될 거다 ㅎ) 코드 #include <cstdio> #include <algorithm> using namespace...
-
[BOJ] 15633 : Fan Death
15633 : Fan Death 풀이 답에서 *5-24하면 되는데 왜 그러는지 모름 ㅋㅋ 코드 #include <cstdio> int n, r; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { if (n % i == 0) r += i; } printf("%d", r*5-24); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 15748 : Rest Stops
15748 : Rest Stops 풀이 그리디하게 풀면 된다. 가장 큰 값까지 간 다음 가능한 시간 동안 계속 풀을 뜯어 먹는다. 그리고 이후의 값들 중 가장 큰 값을 찾고 이 동작을 반복한다. 코드 #include <cstdio> #include <algorithm> long long l, n, r, f, b, x[100003], c[100003]; int main() { scanf("%lld %lld %lld %lld", &l, &n, &f, &b); for (int i = 1; i <= n; i++) scanf("%lld %lld", &x[i], &c[i]); for (int i = n; i...
-
[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");...
-
[BOJ] 16118 : 달빛 여우
16118 : 달빛 여우 풀이 다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데 if (dp[now] != current_sum) continue; 위와 같은 동작을 넣은 코드와 그렇지 않은 코드의 시간복잡도가 다르다. (자세히는 모름) 이 문제의 경우, 데이터가 엄청 빡세서 저 동작을 넣어주지 않으면 시간 초과를 받게 된다. 아래의 코드를 참고하자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; int n, m; struct edg { int idx, cnt; ll dst; bool operator...
-
[BOJ] 16113 : 시그널
16113 : 시그널 풀이 잘 짜면 된다 코드 #include <cstdio> #include <cstring> int n, r[100003]; char a[100003], s[20005][5]; int isone(int x) { for (int i = 0; i < 5; i++) if (s[x][i] == '.' || s[x+1][i] == '#') return 0; return 1; } int count(int x) { int ret = 0; for (int i = x; i < x+3; i++) for (int j = 0; j < 5; j++) ret += s[i][j] == '.';...
-
[BOJ] 16112 : 5차 전직
16112 : 5차 전직 풀이 메이플스토리~~ 코드 #include <cstdio> #include <algorithm> int n, k, a[300003]; long long r, s; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a+n); for (int i = n-1; i >= 0; i--) { if (i < k) r += s; s += (long long)a[i]; } printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge,...
-
[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] 15991 : 1, 2, 3 더하기 6
15991 : 1, 2, 3 더하기 6 풀이 둠칫타칫 코드 #include <cstdio> const int m = 1e9+9; int n, t, d[55555]={0,1,1,2,4}; int main() { for (int i = 5; i <= 55555; i++) { d[i] = ((long long)d[i-1]+d[i-2]+d[i-3]) % m; } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%d\n", (d[n/2+1] + d[n/2]) % m); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘,...
-
[BOJ] 15990 : 1, 2, 3 더하기 5
15990 : 1, 2, 3 더하기 5 풀이 계단오르기 아니면 RGB거리 문제랑 비슷하게 풀면 된다 코드 #include <cstdio> const int m = 1e9+9; int n, t, d[3][100001]; int main() { d[0][1] = d[1][2] = d[0][3] = d[1][3] = d[2][3] = 1; for (int i = 4; i <= 100000; i++) { d[0][i] = (d[1][i-1]+d[2][i-1])%m; d[1][i] = (d[0][i-2]+d[2][i-2])%m; d[2][i] = (d[0][i-3]+d[1][i-3])%m; } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%lld\n", ((long long)d[0][n]+d[1][n]+d[2][n])%m); } return 0; }...
-
[BOJ] 15989 : 1, 2, 3 더하기 4
15989 : 1, 2, 3 더하기 4 풀이 계단오르기 문제랑 비슷하게 풀면 된다 중복되는 경우를 배제해야 하므로 2칸 오르는 경우의 수와 3칸 오르는 경우의 수를 따로 구해주자 답은 두 값을 합친 거에 1로만 채우는 경우의 수 1을 더해주면 된다. 코드 #include <cstdio> int n, t, d[2][10001]; int main() { d[0][2] = 1; for (int i = 3; i <= 10000; i++) { d[0][i] = d[0][i-2]+1; d[1][i] = d[0][i-3]+d[1][i-3]+1; } for (scanf("%d", &t); t--;) { scanf("%d",...
-
[BOJ] 15988 : 1, 2, 3 더하기 3
15988 : 1, 2, 3 더하기 3 풀이 간다~~~~~~~~` 코드 #include <cstdio> int n, t, d[1000001]={0,1,2,4}; int main() { for (int i = 4; i <= 1e6; i++) { d[i] = ((long long)d[i-1]+d[i-2]+d[i-3]) % (int)(1e9+9); } for (scanf("%d", &t); t--;) { scanf("%d", &n); printf("%d\n", d[n]); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[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] 15969 : 행복
15969 : 행복 풀이 돌려돌려~ 돌림판~ 코드 #include <cstdio> int n, x, mn = 1e9, mx = -1e9; int main() { scanf("%d", &n); while (n--) { scanf("%d", &x); if (mn > x) mn = x; if (mx < x) mx = x; } printf("%d", mx - mn); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 16043 : Missing Gnomes
16043 : Missing Gnomes 풀이 주어지지 않은 숫자 중 작은 숫자부터 그리디하게 채워넣으면 된다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m, c[100001]; vector<int> a, b, r; int main() { scanf("%d %d", &n, &m); a.resize(m+1); for (int i = 0, x; i < m; i++) { scanf("%d", &a[i]); c[a[i]] = 1; } for (int i = 1; i <= n; i++) { if (!c[i]) b.push_back(i); } int i = 0,...
-
[BOJ] 11581 : 구호물자
11581 : 구호물자 풀이 공.강.시.러 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[102]; vector<int> gph[102]; void dfs(int now) { if (chk[now] == 1) { puts("CYCLE"); exit(0); } chk[now] = 1; for (int nxt : gph[now]) { if (chk[nxt] != 2) dfs(nxt); } chk[now] = 2; } int main() { scanf("%d", &n); for (int i = 1, u; i < n; i++) { scanf("%d", &m); while (m--) { scanf("%d", &u);...
-
[BOJ] 11281 : 2-SAT - 4
11281 : 2-SAT - 4 풀이 참 아프다 니가 너무 아프다 너를 닮은 이 시린 가을이 오면 보고 싶어서 너를 안고 싶어서 가슴이 너를 앓는다 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 10000*2+2; int n, m, cnt, scc[n_], chk[n_], ans[n_]; vi gph[n_]; vector<vi> res; stack<int, vi> stk; int getSCC(int now) { chk[now] = ++cnt; int ret = chk[now]; stk.push(now); for (int nxt :...
-
[BOJ] 11280 : 2-SAT - 3
11280 : 2-SAT - 3 풀이 그리워져 미치도록 사랑한 그날들이 내 잃어버린 날들이 참 많이 웃고 울었던 그때 그 시절의 우리 니가 떠올라 밤새 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 10000*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]) {...
-
[BOJ] 11278 : 2-SAT - 2
11278 : 2-SAT - 2 풀이 어떠니 넌 괜찮니 지금쯤은 나를 잊고 편안해졌니 이젠 우습지 잘 살길 바라면서도 막상 날 잊었을 널 떠올리면 서글퍼 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 20*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]) {...
-
[BOJ] 11277 : 2-SAT - 1
11277 : 2-SAT - 1 풀이 참 아프다 네가 너무 아프다 너를 닮은 이 시린 가을이 오면 보고 싶어서 너를 안고 싶어서 가슴이 너를 앓는다 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 20*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])...
-
[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] 2207 : 가위바위보
2207 : 가위바위보 풀이 어떠니 잘 지냈니 지난 여름 유난히도 힘에 겹더라 올핸 새벽녘엔 제법 쌀쌀한 바람이 어느덧 네가 좋아하던 그 가을이 와 코드 #include <cstdio> #include <stack> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; const int n_ = 10000*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...
-
[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] 10986 : 나머지 합
10986 : 나머지 합 풀이 (a[i] + ... + a[j]) % m = 0의 필요충분조건은 (a[1]+...+a[j]) % m = (a[1]+...+a[i-1]) % m이다. 오잉? 주어진 문제가 나머지가 x인 prefix sum의 개수를 k라고 할 때, k에서 2개를 고르는 경우의 수들의 합을 구하는 문제로 바뀌었다. 코드 #include <cstdio> typedef long long ll; int n, m, x; ll r, s, a[1002]={1}; int main() { scanf("%d %d", &n, &m); while (n--) scanf("%d", &x), a[s=(s+x)%m]++; while (m--) r+=(a[m]*(a[m]-1))/2; printf("%lld", r); return...
-
[BOJ] 14585 : 사수빈탕
14585 : 사수빈탕 풀이 코드 #include <cstdio> typedef long long ll; int n, m, x; ll r, s, a[1002]={1}; int main() { scanf("%d %d", &n, &m); while (n--) scanf("%d", &x), a[s=(s+x)%m]++; while (m--) r+=(a[m]*(a[m]-1))/2; printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 10282 : 해킹
10282 : 해킹 풀이 안녕하세요 다욱스트라입니다 코드 #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m, s; struct edg { int idx, dst; bool operator <(edg A)const { return dst > A.dst; } }; int main() { cin.tie(0); ios_base::sync_with_stdio(0); int tc; for (cin >> tc; tc; tc--) { cin >> n >> m >> s; vector<vector<edg> > gph(n+1); vector<int> dst(n+1, 1e9); priority_queue<edg> pq; for (int i = 0, u, v,...
-
[BOJ] 2056 : 작업
2056 : 작업 풀이 간단한 다이나믹으로 풀어도 되고 위상정렬스럽게 풀어도 된다 코드 #include <cstdio> #include <algorithm> using namespace std; int n, res, dp[10001]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int c, m, x; scanf("%d %d", &c, &m); for (int j = 0; j < m; j++) { scanf("%d", &x); dp[i] = max(dp[i], dp[x]); } res = max(res, dp[i] += c); } printf("%d", res); return 0; }...
-
[BOJ] 2344 : 거울
2344 : 거울 풀이 매일 가슴이 갈라져요 숨이 다 끊어질만큼 울어요 수 천 번 잊었다 외쳐봐도 내 삶은 어느새 벼랑 끝에 서있네요 코드 #include <cstdio> #include <cstring> #define R(N) for(int i=1;i<=N;i++) int n, m, a[1002][1002], num[1002][1002], res[4004]; void go(int x, int y, int s, int d, int cnt) { int dx[] = { -1*s,0 }, dy[] = { 0,+1*s }; while (a[x][y] != -1) { if (a[x][y] == 1) d = (d+1)%2; x += dx[d],...
-
[BOJ] 15686 : 치킨 배달
15686 : 치킨 배달 풀이 삼성 인사 담당자님, 모든 경우의 수를 다 돌려보면 된답니다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m, x, chk[14]; vector<pair<int, int> > a, b; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &x); if (x == 1) a.push_back({ i,j }); if (x == 2) b.push_back({...
-
[BOJ] 2234 : 성곽
2234 : 성곽 풀이 안 돼요 더는 못해요 그대 없이 사는 일 나 때문에 그대 망가진다며 이별을 원한 건 나인데 코드 #include <cstdio> const int dx[] = { 0,-1,0,1 }; const int dy[] = { -1,0,1,0 }; int n, m, a[55][55], c[55][55], cnt[55*55]; int dfs(int x, int y, int num) { int ret = 1; c[x][y] = num; for (int i = 0; i < 4; i++) { int nx = x+dx[i], ny = y+dy[i];...
-
[BOJ] 5214 : 환승
5214 : 환승 풀이 이번 역은 욱제 욱제 역입니다. 수찬이나 사과역으로 갈아타실 고객께서는 이번 역에서 내리시기 바랍니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; const int n_ = 1e5 + 1e3 + 1; int n, k, m, a, i, j, chk[n_]; queue<int> que; vector<int> gph[n_]; int main() { scanf("%d %d %d", &n, &k, &m); for (i = n + 1; i <= n + m; i++) { for (j =...
-
[BOJ] 14465 : 소가 길을 건너간 이유 5
14465 : 소가 길을 건너간 이유 5 풀이 졸리당 코드 #include <cstdio> int n, m, k, cnt, res = 1e9, a[200001]; int main() { scanf("%d %d %d", &n, &m, &k); while (k--) { int x; scanf("%d", &x); a[x+m] = 1; } for (int i = 1; i <= n; i++) { cnt += a[i+m], cnt -= a[i]; if (i >= m && cnt < res) res = cnt; } printf("%d", res); return 0; } 아무말...
-
[BOJ] 2740 : 행렬 곱셈
2740 : 행렬 곱셈 풀이 으갸갸갸갸갸갸가가가각 코드 #include <cstdio> int n, m, k, a[102][102], b[102][102]; int main() { scanf("%d%d",&n,&m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &a[i][j]); scanf("%d %d", &m, &k); for (int i = 0; i < m; i++) for (int j = 0; j < k; j++) scanf("%d", &b[i][j]); for (int i = 0; i < n; i++) { for (int...
-
[BOJ] 10974 : 모든 순열
10974 : 모든 순열 풀이 stl 쪼아~~~ 코드 #include <cstdio> #include <algorithm> int main() { int n, a[9]; scanf("%d", &n); for (int i = 0; i < n; i++) a[i] = i+1; do { for (int i = 0; i < n; i++) printf("%d ", a[i]); puts(""); } while (std::next_permutation(a, a+n)); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이,...
-
[BOJ] 2960 : 에라토스테네스의 체
2960 : 에라토스테네스의 체 풀이 하앙 나도 에라토스테네스처럼 고수이고 싶다 코드 #include <cstdio> int n, k, c, v[1001]; int main() { scanf("%d %d", &n, &k); for (int i = 2; i <= n; i++) { for (int j = 1; i*j <= n; j++) { if (!v[i*j]) c++; v[i*j] = 1; if (c == k) return !printf("%d\n", i*j); } } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨,...
-
[BOJ] 1389 : 케빈 베이컨의 6단계 법칙
1389 : 케빈 베이컨의 6단계 법칙 풀이 돌리고 돌리고 돌리고~ 코드 #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; int n, m, dst[5005]; vector<int> gph[5005]; int bfs(int start) { int ret = 0; queue<int> que; memset(dst, 0, sizeof(dst)); que.push(start); while (!que.empty()) { int now = que.front(); que.pop(); ret += dst[now]; for (int nxt : gph[now]) { if (dst[nxt]) continue; dst[nxt] = dst[now] + 1; que.push(nxt); } } return ret; } int main()...
-
[BOJ] 15683 : 감시
15683 : 감시 풀이 삼성 인사 담당자님 보고 계신가요? 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }; const int R = 1, D = 2, L = 4, U = 8; vector<int> sight[6] = { {}, { R,D,L,U }, { L+R,U+D }, { R+D,D+L,L+U,U+R }, { R+D+L,D+L+U,L+U+R,U+R+D }, { R+D+L+U } }; int n, m; int a[10][10], b[10][10]; struct abc {...
-
[BOJ] 11899 : 괄호 끼워넣기
11899 : 괄호 끼워넣기 풀이 왠지 그냥 짜면 돌아갈 것 같았어 코드 #include <cstdio> #include <stack> using namespace std; char s[55]; stack<char> stk; int main() { scanf("%s", s); for (int i = 0; s[i]; i++) { if (!stk.empty() && stk.top() == '(' && s[i] == ')') stk.pop(); else stk.push(s[i]); } printf("%d", stk.size()); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제...
-
[BOJ] 7469 : K번째 숫자
7469 : K번째 숫자 풀이 구간합 트리를 쫌 변형해보자. 구간합 트리는 [lft, rgt] 구간에 있는 원소들의 합을 관리한다. 여기서! 원소들의 합을 원소들로 바꿔서 관리해주자! 노드를 int: 구간합이 아니라 vector: 구간의 원소들로 관리하는 거다. 구간을 실체화 시켰다고 하면 될라나? 노드가 2*n개이므로 메모리는 O(n log n)으로 충분하다! 이제 각각의 벡터에는 [lft, rgt] 구간의 원소들이 들어있게 되었고, 이제 각각의 벡터를 정렬해주자. 그리고 쿼리가 들어오면, [s, e] 구간에서 x번째 수가 무엇인지 찾아낼 것이다. 그 수를 이분탐색으로 찾아줄 건데 이건...
-
[BOJ] 15973 : 두 박스
15973 : 두 박스 풀이 노가다를 해보자~ 사실 노가다 안 해도 됨 코드 #include <iostream> #include <string> using namespace std; int x[5], y[5]; string gogo() { if (x[0] == x[3] && y[0] == y[3] || x[1] == x[2] && y[0] == y[3] || x[0] == x[3] && y[1] == y[2] || x[1] == x[2] && y[1] == y[2]) return "POINT"; if (x[0] == x[3] && y[2] <= y[0] && y[0] <= y[3] || x[0] ==...
-
[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] 1067 : 이동
1067 : 이동 풀이 . 코드 #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 bit = n >> 1; for (;j>=bit;bit>>=1) j -= bit; j += bit; if (i < j) swap(a[i],a[j]); } for (int len=2;len<=n;len<<=1){ double ang = 2*M_PI/len*(invert?-1:1); base wlen(cos(ang),sin(ang)); for (int i=0;i<n;i+=len){...
-
[BOJ] 1074 : Z
1074 : Z 풀이 약간의 커팅이 필요하다. 코드 #include <cstdio> #include <cstdlib> int n, r, c; void f(int x, int y, int s, int cnt) { if (s == 0 && x == r && y == c) { printf("%d\n", cnt); exit(0); } if (r < x || c < y || x + s*2 <= r || y + s*2 <= c) return; int nx = x + s, ny = y + s,...
-
[BOJ] 10451 : 순열 사이클
10451 : 순열 사이클 풀이 . 코드 #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int t, n; vector<int> a[1001]; int ans, chk[1001]; void dfs(int now) { chk[now] = 1; for (int i = 0; i < a[now].size(); i++) if (chk[a[now][i]] != 1) dfs(a[now][i]); } int main() { cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { int v; cin >> v;...
-
[BOJ] 14226 : 이모티콘
14226 : 이모티콘 풀이 . 코드 #include <cstdio> #include <cstring> int n, dp[12345][23]; int min(int a, int b) { return a < b ? a : b; } int go(int now, int cnt) { if (now == 0 || cnt > 20) return 1e9; if (now == n) return 0; if (dp[now][cnt] != -1) return dp[now][cnt]; int ret = go(now - 1, cnt + 1) + 1; for (int i = 2; i * now...
-
[BOJ] 1415 : 사탕
1415 : 사탕 풀이 . 코드 #include <cstdio> #include <vector> using namespace std; int n, ccnt[10001]; long long d[500005]; vector<int> cvec; bool p[500005]; void getprimes() { for (int i = 2; i <= 500000; i++) p[i] = 1; for (int i = 2; i*i <= 500000; i++) if (p[i]) for (int j = i*i; j <= 500000; j += i) p[j] = 0; } int main() { getprimes(); scanf("%d", &n); int zcnt = 1; d[0]...
-
[BOJ] 12842 : 튀김 소보루
12842 : 튀김 소보루 풀이 . 코드 #include <cstdio> int n, m, time, idx, a[100001]; int main() { scanf("%d %d", &n, &m); n -= m; scanf("%d", &m); for (int i = 1; i <= m; i++) scanf("%d", a + i); while (n) { for (int i = 1; i <= m; i++) { if (time % a[i] == 0) { n--; idx = i; if (!n) break; } } time++; } printf("%d\n", idx); return 0;...
-
[BOJ] 12841 : 정보대 등산
12841 : 정보대 등산 풀이 누적합! 코드 #include <cstdio> typedef long long ll; int n, i; ll a[100001], b[100001], c[100002]; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%lld", c + i); for (i = 2; i <= n; i++) scanf("%lld", a + i), a[i] += a[i-1]; for (i = 2; i <= n; i++) scanf("%lld", b + i), b[i] += b[i-1]; ll pos = 1, sum = 1e18; for...
-
[BOJ] 12840 : 창용이의 시계
12840 : 창용이의 시계 풀이 , 코드 #include <cstdio> int main() { int h, m, s, tc, t, c, mod = 86400; scanf("%d %d %d", &h, &m, &s); s += m * 60 + h * 3600; for (scanf("%d", &tc); tc; tc--) { scanf("%d", &t); if (t == 1) scanf("%d", &c), s = (s + c) % mod; if (t == 2) scanf("%d", &c), s = (s - c) % mod; if (t == 3)...
-
[BOJ] 1866 : 택배
1866 : 택배 풀이 , 코드 #include <cstdio> #include <algorithm> using namespace std; int n, t, h, a[3003], dp[3003]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d %d", &t, &h); sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + a[i] * t; int cst = h; for (int j = i;...
-
[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] 7562 : 나이트의 이동
7562 : 나이트의 이동 풀이 . 코드 #include <cstdio> #include <cstring> #include <queue> using namespace std; typedef pair<int, int> pii; const int dx[] = { 1,2,2,1,-1,-2,-2,-1 }; const int dy[] = { -2,-1,1,2,2,1,-1,-2 }; int n, x, y, a, b, dst[303][303]; queue<pii> que; int main() { int tc; for (scanf("%d", &tc); tc; tc--) { scanf("%d %d %d %d %d", &n, &x, &y, &a, &b); que.push({ x,y }); dst[x][y] = 1; while (!que.empty()) { pii now...
-
[BOJ] 10804 : 카드 역배치
10804 : 카드 역배치 풀이 . 코드 #include <cstdio> #include <algorithm> using namespace std; int n = 10, a[21]; int main() { int l, r; for (int i=1;i<=20;i++) a[i] = i; while (n--) { scanf("%d %d", &l, &r); reverse(a + l, a + r + 1); } for (int i=1;i<=20;i++) { printf("%d ", a[i]); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘,...
-
[BOJ] 1506 : 경찰서
1506 : 경찰서 풀이 . 코드 #include <cstdio> int n, ans, c[101], v[101]; char a[101][101]; int main() { int i, j, k; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &c[i]); for (i = 0; i < n; i++) scanf("%s", a[i]); for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) a[i][j] |= a[i][k] & a[k][j]; for (i...
-
[BOJ] 14501 : 퇴사
14501 : 퇴사 풀이 . 코드 #include <cstdio> int max(int a, int b) { return a > b ? a : b; } int n, t, p, d[22]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &t, &p); d[i + 1] = max(d[i + 1], d[i]); d[i + t] = max(d[i + t], d[i] + p); } printf("%d", d[n]); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 15678 : 연세워터파크
15678 : 연세워터파크 풀이 . 코드 #include <cstdio> #include <algorithm> #include <deque> using namespace std; typedef pair<long long, int> pli; int n, d; long long a, now, ans = -1e9; deque<pli> deq; int main() { scanf("%d %d", &n, &d); for (int i = 1; i <= n; i++) { scanf("%lld", &a); while (!deq.empty() && deq.front().second + d < i) deq.pop_front(); now = max(a, a + deq.front().first); ans = max(ans, now); while (!deq.empty() && deq.back().first <=...
-
[BOJ] 15670 : 도로 공사
15670 : 도로 공사 풀이 구현이 좀 귀찮은데 잘 따져서 슥슥 짜주면 된다. 코드 #include <cstdio> int n, m, i, x, y, a[100002]; int inc[100002], dec[100002]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) scanf("%d", &a[i]); inc[1] = dec[1] = 1; for (i = 2; i <= n; i++) inc[i] = inc[i - 1] + (a[i - 1] >= a[i]); for (i = 2; i <= n; i++)...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 잘 짜주자. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return !printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now == del) { cnt--; break; }...
-
[BOJ] 15668 : 방 번호
15668 : 방 번호 풀이 적당히 큰 수까지 어떻게 잘 돌려주면 된다. 코드 #include <cstdio> #include <cstring> #include <algorithm> int n, ans, cnt[10]; int main() { scanf("%d", &n); for (int i = 1; i < std::min(n, 98765); i++) { memset(cnt, 0, sizeof(cnt)); int a = i, b = n - i, flag = 1; while (a) cnt[a % 10]++, a /= 10; while (b) cnt[b % 10]++, b /= 10; for (int j = 0;...
-
[BOJ] 15667 : 2018 연세대학교 프로그래밍 경진대회
15667 : 2018 연세대학교 프로그래밍 경진대회 풀이 폭죽이 폭발하는 경우를 수식으로 잘 나타내서 정리해보자. n = x^2 + x + 1 = x(x+1) + 1 n - 1 = x * (x + 1) 이제 리니어하게 탐색해주자. 코드 #include <cstdio> int main() { int n; scanf("%d", &n); n--; for (int i = 1; i <= n; i++) { if (i * (i + 1) == n) { printf("%d", i); return 0; } } return 0;...
-
[BOJ] 10547 : STUDENTSKO
COCI 2014/2015 Contest #2 3번 10547 : STUDENTSKO 풀이 한 팀에 들어가야 하는 학생들에게 같은 그룹 넘버를 부여하자 그냥 부여하는 건 아니고 먼저 뽑혀야하는 팀부터 오름차순으로 부여하자 그리고 가장 긴 단조증가하는 수열의 길이를 구하자. 코드 #include <cstdio> #include <algorithm> using namespace std; int n, k, len, a[5005], lis[5005]; pair<int, int> p[5005]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) scanf("%d", &a[i]), p[i].first = a[i]; sort(a, a +...
-
[BOJ] 10546 : 배부른 마라토너
COCI 2014/2015 Contest #2 2번 10546 : 배부른 마라토너 10546 : UTRKA 풀이 map 써도 되고 이렇게 짜도 된다 코드 #include <cstdio> int n, i; char a[22], s[22]; int main() { scanf("%d", &n); n *= 2; for (n--; n--;) { scanf("%s", s); for (i = 0; s[i]; i++) a[i] ^= s[i]; } printf("%s", a); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 10545 : 뚜기뚜기메뚜기
COCI 2014/2015 Contest #2 1번 10545 : 뚜기뚜기메뚜기 10545 : MOBITEL 풀이 으쌰으쌰 잘 짜보자. 코드 #include <cstdio> int m[11], t[33] = { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9 }; char s[111]; int main() { for (int i = 1, a; i <= 9; i++) scanf("%d", &a), m[a] = i; scanf("%s", s + 1); for (int i = 1, now, prv = -1; s[i]; i++) { now = t[s[i] - 'a']; if (prv == now) printf("#"); for (int j =...
-
[BOJ] 15562 : 네트워크
15562 : 네트워크 풀이 모든 정점에 대한 sum(max(outdegree - indegree, 0))이 답이다. for (i = 1 ~ n) ans += max(out[i] - in[i], 0); for (i = 1 ~ n) ans += d[i]; ans /= 2; for (i = 1 ~ n) ans += max(d[i], 0); 등등 degree를 관리하는 방식에 따라 같은 식을 여러가지로 변형할 수 있겠다. 어떤 정점의 outdegree가 indegree보다 크다는 것은 해당 정점을 하나보다 많은 네트워크로 분리해서 나누어서 다음 노드로 나아가야 함을 의미한다....
-
[BOJ] 15561 : 구간 합 최대? 2
15561 : 구간 합 최대? 2 풀이 max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i)) = max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V 모든 A[i]를 U * A[i] + V로 바꿔주면 max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다. 15560번에 비해 범위가 크므로 세그먼트 트리 등등을 이용해주자. 코드 #include <cstdio> #include <algorithm>...
-
[BOJ] 15560 : 구간 합 최대? 1
15560 : 구간 합 최대? 1 풀이 max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i)) = max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V 모든 A[i]를 U * A[i] + V로 바꿔주면 max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다. 15561번 풀이에 세그트리를 이용한 구현이 있다. 여긴 나이브한 구현. 코드 #include <cstdio> int...
-
[BOJ] 3108 : 로고
3108 : 로고 풀이 사각형을 하나의 노드로 보자. 어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자. 연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다. 연필은 연결 요소의 개수 - 1번 들어주면 된다. 단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자. (x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다. Flood fill로 풀어도 된다. 코드 #include <cstdio> #include <algorithm> #define y1 fu using namespace std; const int n_ = 1000 +...
-
[BOJ] 14557 : Memory
14557 : Memory 풀이 봄이 그렇게도 좋냐 멍청이들아 코드 main(a,b){scanf("%d%d",&a,&b);printf("%d %d",a*b/2,a*b-1);} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2669 : 직사각형 네개의 합집합의 면적 구하기
2669 : 직사각형 네개의 합집합의 면적 구하기 풀이 으아아아ㅏ 코드 #include <cstdio> int k, i, j, x1, x2, y1, y2, a[101][101]; int main() { for (; k < 4; k++) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); for (i = x1; i < x2; i++) for (j = y1; j < y2; j++) a[i][j] = 1; } for (i = 1; i <= 100; i++) for (j = 1; j <= 100; j++)...
-
[BOJ] 10093 : 숫자
10093 : 숫자 풀이 알잖아 너를 이토록 사랑하며 기다린 나를 뭐가 그리 바쁜지 너무 보기 힘들어 넌 도대체 뭐하고 다니니 코드 #include <cstdio> #include <algorithm> int main() { long long a, b; scanf("%lld %lld", &a, &b); if (a > b) std::swap(a, b); printf("%lld\n", b > a ? b - a - 1 : 0); for (++a; a < b; printf("%lld ", a++)); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C,...
-
[BOJ] 2563 : 색종이
2563 : 색종이 풀이 랭작조아 코드 #include <cstdio> int n, r, x, y, i, j, a[101][101]; int main() { scanf("%d", &n); while (n--) { scanf("%d %d", &x, &y); for (i = x; i < x + 10; i++) for (j = y; j < y + 10; j++) r += !a[i][j]++; } printf("%d", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 1850 : 최대공약수
1850 : 최대공약수 풀이 뚜룹뚜빠라빠라 코드 #include <cstdio> typedef long long ll; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll a, b; int main() { scanf("%lld %lld", &a, &b); int r = gcd(a, b); while (r--) printf("1"); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1915 : 가장 큰 정사각형
1915 : 가장 큰 정사각형 풀이 d[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1] (if a[i][j] != 0) 코드 #include <cstdio> #include <algorithm> int n, m, i, j, r, a, d[1003][1003]; int main() { scanf("%d %d", &n, &m); for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) { scanf("%1d", &a); if (!a) continue; d[i][j] = std::min({ d[i-1][j],d[i][j-1],d[i-1][j-1] }) + 1; r = std::max(r, d[i][j]); } printf("%d", r*r); return 0; } 아무말...
-
[BOJ] 2587 : 대표값2
2587 : 대표값2 풀이 후후 코드 #include <cstdio> #include <algorithm> int i, s, a[5]; int main() { for (; i < 5; i++) scanf("%d", &a[i]), s += a[i]; std::sort(a, a + 5); printf("%d\n%d", s / 5, a[2]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2592 : 대표값
2592 : 대표값 풀이 히히 코드 #include <cstdio> int i, a, s, c[1001]; int main() { for (; i < 10; i++) scanf("%d", &a), s += a, c[a]++; for (; i < 1000; i += 10) if (c[c[0]] < c[i]) c[0] = i; printf("%d\n%d", s / 10, c[0]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2754 : 학점계산
2754 : 학점계산 풀이 호호 코드 #include <cstdio> int tc; double r; char s[3]; int main() { scanf("%s", s); if (s[0] == 'A') r = 4; if (s[0] == 'C') r = 2; if (s[0] == 'B') r = 3; if (s[0] == 'D') r = 1; if (s[1] == '+') r += 0.3; if (s[1] == '-') r -= 0.3; printf("%.1lf", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge,...
-
[BOJ] 2755 : 이번학기 평점은 몇점?
2755 : 이번학기 평점은 몇점? 풀이 하하 코드 #include <cstdio> int tc, hak, cnt; double res, tmp; char sbj[103], sco[3]; int main() { for (scanf("%d", &tc); tc--;) { scanf("%s %d %s", sbj, &hak, sco); if (sco[0] == 'A') tmp = 4; if (sco[0] == 'C') tmp = 2; if (sco[0] == 'B') tmp = 3; if (sco[0] == 'D') tmp = 1; if (sco[1] == '+') tmp += 0.3; if (sco[1] == '-') tmp -=...
-
[BOJ] 9047 : 6174
9047 : 6174 풀이 오후수업개꿀 코드 #include <cstdio> #include <functional> #include <algorithm> using namespace std; int main() { int tc; for (scanf("%d", &tc); tc--;) { int i, c = 0, a[5], b[5]; for (i = 0; i < 4; i++) scanf(" %1d", &a[i]); while (a[0] != 6 || a[1] != 1 || a[2] != 7 || a[3] != 4) { b[0] = a[0], b[1] = a[1], b[2] = a[2], b[3] = a[3]; sort(a, a +...
-
[BOJ] 1377 : 버블 소트
1377 : 버블 소트 풀이 몇 번 움직였는지 세어보자 코드 #include <cstdio> #include <algorithm> using namespace std; int n, i, r; pair<int, int> p[500005]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &p[i].first), p[i].second = i; sort(p, p + n); for (i = 0; i < n; i++) r = max(r, p[i].second - i); printf("%d", r + 1); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 3047 : ABC
3047 : ABC 풀이 꺄르르르르르르륵 코드 #include <cstdio> #include <algorithm> int a[5]; char b[5]; int main() { scanf("%d %d %d %s", &a[0], &a[1], &a[2], b); std::sort(a, a + 3); printf("%d %d %d", a[b[0] - 'A'], a[b[1] - 'A'], a[b[2] - 'A']); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1964 : 5각형, 5각형, 5각형...
1964 : 5각형, 5각형, 5각형… 풀이 알잖아 너를 이토록 사랑하며 기다린 나를~ 코드 main(n){printf("%d",scanf("%d",&n)+n*(3ll*n+5)/2%45678);} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1373 : 2진수 8진수
1373 : 2진수 8진수 풀이 가나다라마바사 코드 #include <cstdio> int i, j; char c[1000005] = { '0','0' }; int main() { scanf("%s", c + 2); while (c[i]) c[i++] -= '0'; for (j = i % 3; j < i; j += 3) printf("%d", c[j]*4 + c[j+1]*2 + c[j+2]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1371 : 가장 많은 글자
1371 : 가장 많은 글자 풀이 어디에도 그대가 살아서 코드 #include <cstdio> int ans, cnt[33]; char c; int main() { while (~scanf("%c", &c)) cnt[c - 'a']++; for (c = 0; c < 26; c++) ans = ans > cnt[c] ? ans : cnt[c]; for (c = 0; c < 26; c++) if (cnt[c] == ans) printf("%c", c + 'a'); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠,...
-
[BOJ] 1357 : 뒤집힌 덧셈
1357 : 뒤집힌 덧셈 풀이 돌리고 돌리고 돌리고~ 코드 #include <cstdio> int f(int n) { int r = 0; while (n) r *= 10, r += n % 10, n /= 10; return r; } int main() { int a, b; scanf("%d %d", &a, &b); printf("%d", f(f(a) + f(b))); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1312 : 소수
1312 : 소수 풀이 언젠가는 돌아갈게 사랑할 자격 갖춘 나 되어 코드 #include <cstdio> int a, b, c, n; int main() { scanf("%d %d %d", &a, &b, &n); while (n--) a %= b, a *= 10, c = a / b; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 6118 : 숨바꼭질
6118 : 숨바꼭질 풀이 최단경로 가즈아~~~ 코드 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int n_ = 20000 + 2; int n, m, a, b, c, dst[n_]; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0, u, v; i < m; i++) { scanf("%d %d", &u, &v); gph[u].push_back(v); gph[v].push_back(u); } queue<int> que; que.push(1); while (!que.empty()) { int now = que.front(); que.pop(); for (int nxt :...
-
[BOJ] 4781 : 사탕 가게
4781 : 사탕 가게 풀이 윽 코드 #include <cstdio> #include <cstring> int n, m, m1, m2, dp[10001]; inline int max(int a, int b) { return a > b ? a : b; } int main() { while (1) { scanf("%d %d.%d", &n, &m1, &m2); if (!n) break; memset(dp, 0, sizeof(dp)); m = m1 * 100 + m2; int ans = 0; for (int i = 0, c, p; i < n; i++) { scanf("%d %d.%d",...
-
[BOJ] 13324 : boj 수열 2
13324 : boj 수열 2 풀이 끙 풀이를 뭐라고 적지 코드 #include <cstdio> #include <queue> using namespace std; int n, i, a, ans[1000001]; priority_queue<int> pq; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%d", &a); a -= i; pq.push(a); pq.push(a); pq.pop(); ans[i] = pq.top(); } --i; while (--i) if (ans[i] > ans[i + 1]) ans[i] = ans[i + 1]; for (i = 1; i <= n; i++) printf("%d\n", ans[i]...
-
[BOJ] 13323 : boj 수열 1
13323 : boj 수열 1 풀이 13324번 풀이를 참고하자 코드 #include <cstdio> #include <queue> using namespace std; int n; long long sum; priority_queue<int> pq; int main() { scanf("%d", &n); for (int i = 0, a; i < n; i++) { scanf("%d", &a); a -= i; pq.push(a); if (!pq.empty() && pq.top() > a) { sum += pq.top() - a; pq.pop(); pq.push(a); } } printf("%lld", sum); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 15559 : 내 선물을 받아줘
15559 : 내 선물을 받아줘 풀이 boj에 내가 나왔으면 정말 좋겠네~ 정말 좋겠네~~~~ 코드 #include <iostream> using namespace std; int n, m, i, j, ans, cnt = 1, vst[1001][1001]; char a[1001][1001]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i < n; i++) for (j = 0; j < m; j++) { if (vst[i][j]) continue; int y =...
-
[BOJ] 5527 : 전구 장식
5527 : 전구 장식 풀이 다음과 같이 전구가 번갈아 켜진 구간 [x, y]들이 연속되어 있다고 하자. [a, b] [c, d] [e, f] 여기서 (b c), (d e)는 서로 같은 상태(둘 다 켜지거나 꺼지거나)라고 가정하자. 여기서 [c, d] 구간을 flip 해주면 전체 [a, f] 구간이 번갈아 켜지게 된다. 띠용? 코드 #include <cstdio> #include <algorithm> int n, ans, pos = 1, cnt[100001]; int main() { scanf("%d", &n); for (int i = 0, a = -1, b; i...
-
[BOJ] 9489 : 사촌
9489 : 사촌 풀이 부모를 찾으러 산으로 갈까요~ 사촌을 찾으러 강으로 갈까요~ 코드 #include <cstdio> int main() { while (1) { int n, k, a[1111] = { -1 }, p[1111] = { -1 }; scanf("%d %d", &n, &k); if (!n && !k) break; int cnt = -1, idx = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); if (a[i] == k) idx = i; if (a[i] != a[i - 1]...
-
[BOJ] 14815 : Fresh Chocolate (Small)
14815 : Fresh Chocolate (Small) 풀이 룰루랄라 코드 #include <cstdio> #include <algorithm> using namespace std; int main() { int tc, t, n, p, c[5]; scanf("%d", &tc); for (t = 1; t <= tc; t++) { c[0] = c[1] = c[2] = c[3] = 0; scanf("%d %d", &n, &p); for (int i = 0, a; i < n; i++) scanf("%d", &a), c[a % p]++; int r = c[0]; if (p == 2) { r += (c[1]...
-
[BOJ] 14816 : Fresh Chocolate (Large)
14816 : Fresh Chocolate (Large) 풀이 뭔가 제너럴한 규칙을 찾으려고 했는데 잘 모르겠당 p가 2~4밖에 안 되므로 그냥 경우를 나눠서 잘 따져주자. 코드 #include <cstdio> #include <algorithm> using namespace std; int main() { int tc, t, n, p, c[5]; scanf("%d", &tc); for (t = 1; t <= tc; t++) { c[0] = c[1] = c[2] = c[3] = 0; scanf("%d %d", &n, &p); for (int i = 0, a; i < n; i++) scanf("%d", &a),...
-
[BOJ] 12784 : 인하니카 공화국
12784 : 인하니카 공화국 풀이 루트부터 내려가서 자식들을 끊는 게 좋을지 부모를 끊는 게 좋을지 봐보자. 코드 #include <cstdio> #include <vector> using namespace std; struct edg { int idx, dst; }; vector<edg> gph[1001]; int dfs(int prv, int now, int dst) { int ret = 0; for (edg nxt : gph[now]) if (prv != nxt.idx) ret += dfs(now, nxt.idx, nxt.dst); if (!ret) ret = dst; return ret < dst ? ret : dst; } int main()...
-
[BOJ] 11585 : 속타는 저녁 메뉴
11585 : 속타는 저녁 메뉴 풀이 원순열을 구현하려면 귀찮으니까 똑같은 문자열을 두 번 이어붙여주자 그리고 kmp를 돌려서 substring으로 등장하는 횟수를 구해주자 코드 #include <cstdio> const int n_ = 1e6 + 5; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } int n, i, j, cnt, fail[n_]; char a[n_], b[n_ * 2]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf(" %c", &a[i]); for (i =...
-
[BOJ] 6209 : 제자리 멀리뛰기
6209 : 제자리 멀리뛰기 풀이 이분탐색을 해주자 mid를 최소로 뛰는 거리로 두고 파라메트릭 해주자. 코드 #include <cstdio> #include <algorithm> using namespace std; int d, n, m, a[50005]; int main() { scanf("%d %d %d", &d, &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); a[n + 1] = d; sort(a + 1, a + n + 1); int lft = 0, rgt = d, ans; while (lft <= rgt) { int mid...
-
[BOJ] 11728 : 배열 합치기
11728 : 배열 합치기 풀이 조아조아조아조아조아 코드 #include <cstdio> #include <algorithm> int a, b, c[2000001]; int main() { scanf("%d %d", &a, &b); a = b = a + b; while (a--) scanf("%d", &c[a]); std::sort(c, c + b); for (a = 0; a < b; a++) printf("%d ", c[a]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1402 : 아무래도이문제는A번난이도인것같다
1402 : 아무래도이문제는A번난이도인것같다 풀이 a * 1 * 1 * 1 ... 이런 식으로 모든 수를 만들 수 있다. 코드 main(t){for(scanf("%d",&t);t--;)puts("yes");} 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 3460 : 이진수
3460 : 이진수 풀이 종강 언제지 코드 #include <cstdio> int main() { int tc; for (scanf("%d", &tc); tc; tc--) { int a, i = 0; scanf("%d", &a); while (a) { if (a & 1) printf("%d ", i); a >>= 1, i++; } puts(""); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 3449 : 해밍 거리
3449 : 해밍 거리 풀이 끄아아아아 코드 #include <iostream> #include <string> using namespace std; int n; string a, b; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; while (n--) { int r = 0; cin >> a >> b; for (int i = 0; i < a.size(); i++) if (a[i] != b[i]) r++; cout << "Hamming distance is " << r << ".\n"; } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 3040 : 백설 공주와 일곱 난쟁이
3040 : 백설 공주와 일곱 난쟁이 풀이 일단 다 더해놓고 2개씩 빼보자 코드 #include <cstdio> int s, a[11]; int main() { for (int i = 0; i < 9; i++) scanf("%d", a + i), s += a[i]; for (int i = 0; i < 9; i++) for (int j = i; j < 9; j++) if (i != j && s - a[i] - a[j] == 100) for (int k = 0; k < 9;...
-
[BOJ] 7572 : 간지
7572 : 간지 풀이 나는 몰랐네 그대 마음 변할 줄은 난 정말 몰랐었네 코드 main(n) { scanf("%d",&n); printf("%c%d",(n+8)%12+'A',(n+6)%10); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1356 : 유진수
1356 : 유진수 풀이 아 이별이 그리 쉬운가 세월 가버렸다고 이젠 나를 잊고서 멀리 멀리 떠나가는가 코드 #include <cstdio> int i, j, l; char s[11]; int main() { scanf("%s", s + 1); for (i = 1; s[i]; i++); l = i - 1; for (i = 1; i < l; i++) { int s1 = 1, s2 = 1; for (j = 1; j <= i; j++) s1 *= (s[j] - '0'); for (j =...
-
[BOJ] 1302 : 베스트셀러
1302 : 베스트셀러 풀이 다정했던 사람이여 나를 잊었나 벌써 나를 잊어버렸나 코드 #include <iostream> #include <string> #include <map> using namespace std; int n, rn; string s, rs; map<string, int> m; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; while (n--) cin >> s, m[s]++; for (auto it : m) if (rn < it.second) rn = it.second, rs = it.first; cout << rs; return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C,...
-
[BOJ] 1297 : TV 크기
1297 : TV 크기 풀이 수학 조아!!! 가로 세로 n:m의 비율이 주어지면 이 때의 대각선 비율을 d라고 하자. 이제 이걸 주어진 대각선 길이에 맞춰 나누고 곱하고 으쌰으쌰 해보자. 코드 #include <cstdio> #include <cmath> int main() { int k, a, b; scanf("%d %d %d", &k, &a, &b); double d = k/sqrt(a*a+b*b); printf("%d %d", (int)(a*d), (int)(b*d)); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 2293 : 동전 1
2293 : 동전 1 풀이 dp[i] = 동전 i원을 만들 수 있는 방법의 수 dp[i] = dp[i - coins[]] 코드 main() { int N, K, x, i, j; int dp[10001] = { 1, }; scanf("%d %d", &N, &K); for (i = 1; i <= N; i++) { scanf("%d", &x); for (j = 0; j <= K - x; j++) dp[j + x] += dp[j]; } printf("%d", dp[K]); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon...
-
[BOJ] 1225 : 이상한 곱셈
1225 : 이상한 곱셈 풀이 눈누난 코드 #include <cstdio> long long i, s, r; char a[10001], b[10001]; int main() { scanf("%s %s", a, b); for (i = 0; a[i]; i++) s += a[i] - '0'; for (i = 0; b[i]; i++) r += s * (b[i] - '0'); printf("%lld", r); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이...
-
[BOJ] 1011 : Fly me to the Alpha Centauri
1011 : Fly me to the Alpha Centauri 풀이 1 2 3 ... i-1 i i-1 ... 3 2 1 이렇게 삼각형으로 증가/감소하는 수열 s를 생각해보자. s의 원소들의 합은 i^2이다. dist = end - start일 때, dist가 음수가 되지 않는 가장 큰 i를 골라서 dist - i^2를 해주자. 남은 거리는 1와 i 사이에 숫자를 잘 골라서 채워넣을 수 있다. 코드 #include <stdio.h> #include <math.h> int main() { int tc; for (scanf("%d", &tc); tc; tc--) {...
-
[BOJ] 10870 : 피보나치 수 5
10870 : 피보나치 수 5 풀이 엠티 가즈아~ 코드 #include <stdio.h> int n, a, b = 1; int main() { scanf("%d", &n); while (n--) { b += a; a = b - a; } printf("%d", a); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11727 : 2xn 타일링 2
11727 : 2xn 타일링 2 풀이 끄으 코드 main() { int n, a = 0, b = 1, i; scanf("%d", &n); for (i = 0; i < n; ++i) { b += a * 2; a = b - a * 2; b %= 10007; } printf("%d", b); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11726 : 2xn 타일링
11726 : 2xn 타일링 풀이 쓰기 귀찮다 다른 블로그에 그림이 포함된 친절한 풀이가 많으니 다른 블로그를 참고 해주시면 감사하겠습니다. 코드 #include <stdio.h> int n, dp[1010]; int main() { dp[0] = dp[1] = 1; scanf("%d", &n); for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % 10007; printf("%d", dp[n] % 10007); return 0; } main(n,a,b) { scanf("%d",&n); a=b=1; while(n--) { b+=a; a=b-a; b%=10007; } printf("%d",a); } 아무말...
-
[BOJ] 1188 : 음식 평론가
1188 : 음식 평론가 풀이 n과 m의 최대공약수를 이용해 문제에 접근해보자. n과 m이 서로소인 경우, 서로소가 아닌 경우로 나눌 수 있다. g = gcd(n, m)이라고 하자. f(n, m)을 n과 m에 대한 답을 구하는 함수라고 하자. f(n, m) = f(n/g, m/g) * g임은 자명하게 알 수 있다. 그러므로 g != 1인 경우의 답은 g = 1인 경우의 답을 알면 구할 수 있고 우린 모든 경우에 대해 답을 구할 수 있게 된다. 어떤 a, b에 대해서 gcd(a,...
-
[BOJ] 1145 : 적어도 대부분의 배수
1145 : 적어도 대부분의 배수 풀이 조아~ 코드 #include <stdio.h> int i,j,c,a[5]; int main() { for (i=0;i<5;i++)scanf("%d",&a[i]); for (i=1;;i++){ for(j=0,c=0;j<5;j++)if(i%a[j]==0)c++; if(c>=3)return ~printf("%d",i); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1120 : 문자열
1120 : 문자열 풀이 그리디하게 풀어보자. a의 길이가 b보다 짧으므로 a[i] != b[j]의 개수가 가장 짧은 구간을 택하면 아무 문자나 양옆으로 붙일 수 있으므로 최소의 a[i] != b[j] 합이 답이 된다. 코드 #include <cstdio> #include <cstring> char a[55], b[55]; int alen, blen, sum, min = 1e9, i, j; int main() { scanf("%s %s", a, b); alen = strlen(a); for (; b[i + alen - 1]; i++, sum = 0) { for (j = 0; a[j];...
-
[BOJ] 1075 : 나누기
1075 : 나누기 풀이 저 푸른 초원 위에 그림 같은 집을 짓고 코드 #include <stdio.h> int a, b, i; int main() { scanf("%d %d", &a, &b); a /= 100; a *= 100; for (; i <= 100; i++) if ((a + i) % b == 0) return ~printf("%02d", (a + i) % 100); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제,...
-
[BOJ] 1015 : 수열 정렬
1015 : 수열 정렬 풀이 졸리다 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, i, b[55]; pair<int, int> a[55]; int main() { scanf("%d", &n); while (i < n) scanf("%d", &a[i].first), a[i].second = i, i++; sort(a, a + n); while (i--) b[a[i].second] = i; i++; while (i < n) printf("%d ", b[i++]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제,...
-
[BOJ] 1806 : 부분합
1806 : 부분합 풀이 종강 언제지 코드 #include <stdio.h> #include <algorithm> int n, m, r = 1e9, a[100001]; int main() { scanf("%d %d", &n, &m); for (int i = 1, j = 0; i <= n; i++) { scanf("%d", &a[i]); a[i] += a[i - 1]; for (; a[i] - a[j] >= m; j++) r = std::min(r, i - j); } printf("%d", r == 1e9 ? 0 : r); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 2003 : 수들의 합 2
2003 : 수들의 합 2 풀이 투포인터 조아!! 분할정복도 조아!! 코드 #include <stdio.h> int n, m, k, s, a[10001]; int main() { scanf("%d %d", &n, &m); for (int i = 0, j = 0; i < n; i++) { scanf("%d", &a[i]); s += a[i]; while (s > m) s -= a[j++]; k += (s == m); } printf("%d", k); return 0; } #include <cstdio> #include <algorithm> using namespace std; int n, k, a[10001], sum[10001]; int...
-
[BOJ] 1493 : 박스 채우기
1493 : 박스 채우기 풀이 ! 큐브러버님 코드 참고했습니다 ! 가장 큰 큐브부터 사용해서 박스를 채워야 하는 것은 증명할 것도 없이 자명하다. 부피로 으쌰으쌰 슥삭슥삭 멋있게 잘 계산해서 빈 공간을 잘 채워넣으면 된다. 사용했던 큐브를 보다 작은 단위로 쪼개나가자. 1*1*1 단위까지 쪼개지면, 그 큐브의 개수가 박스의 부피와 같은지를 비교해주자. 코드 #include <cstdio> #include <algorithm> typedef long long ll; int l, w, h, n; int a[22]; ll cnt, ans; int main() { scanf("%d %d %d %d",...
-
[BOJ] 12025 : 장난꾸러기 영훈
12025 : 장난꾸러기 영훈 풀이 아 9시 수업 에반데 코드 #include <stdio.h> long long i, k; char s[66]; int main() { scanf("%s %lld", s, &k); k--; for (i = 0; s[i]; i++) { if (s[i] == '6' || s[i] == '7') s[i] -= 5; } while (i--) { if (s[i] == '1' || s[i] == '2') { if (k & 1) s[i] += 5; k >>= 1; } } puts(k ? "-1" : s); return...
-
[BOJ] 2212 : 센서
2212 : 센서 풀이 각각의 좌표들을 정렬해보자. 그리고 인접한 좌표들의 거리 차이를 구해보자. 그리고 그 거리 차이를 다시 정렬해보자. k개의 집중국, 다시 말해 k개의 직선을 놓는다면 k-1개의 빈 공간(?)이 생기게 만들 수 있다. 그러므로 방금 정렬한 거리 차이 중에서 가장 큰 값을 k-1개 고르면 집중국이 차지하는 영역(?)의 합이 최소가 될 것이고 답을 구할 수 있다 (!!) 코드 #include <stdio.h> #include <algorithm> int n, k, ans, a[10001]; int main() { scanf("%d %d", &n, &k); for (int...
-
[BOJ] 1969 : DNA
1969 : DNA 풀이 음 사실 그리디인지는 잘 모르겠고 그냥 나이브하게 짜면 된다. 코드 #include <stdio.h> int n, m, d, cnt[51][26]; char s[1001][51], r[1001]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%s", s[i]); for (int j = 0; j < m; j++) cnt[j][s[i][j] - 'A']++; } for (int i = 0; i < m; i++) { int mx = 0; for (int j = 0;...
-
[BOJ] 2217 : 로프
2217 : 로프 풀이 로프의 무게를 내림차순으로 정렬해서 무게를 달아보자! i번째 로프에 걸리는 중량은 weight / i이다. 가장 튼튼한 로프에 걸리는 중량을 w[1]이라고 할 때 w[i] (i != 1)은 항상 w[1]보다 작으므로 중량을 하나씩 걸어보면서 max값을 찾으면 된다. 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, a[100001], k = -1; scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%d", &a[i]); std::sort(a, a + n); for (i = 0; i <...
-
[BOJ] 1793 : 타일링
1793 : 타일링 풀이 타일링 가즈아~~~!!! 코드 #include <iostream> #include <string> #include <algorithm> using namespace std; int n; string dp[255] = { "1", "1" }; string deohagi(string a, string b) { int sum = 0; string res; while (!a.empty() || !b.empty() || sum) { if (!a.empty()) sum += a.back() - '0', a.pop_back(); if (!b.empty()) sum += b.back() - '0', b.pop_back(); res.push_back((sum % 10) + '0'); sum /= 10; } reverse(res.begin(), res.end()); return res; } int...
-
[BOJ] 10757 : 큰 수 A+B
10757 : 큰 수 A+B 풀이 더하기 가즈아~! 코드 #include <iostream> #include <string> #include <algorithm> using namespace std; string deohagi(string a, string b) { int sum = 0; string res; while (!a.empty() || !b.empty() || sum) { if (!a.empty()) sum += a.back() - '0', a.pop_back(); if (!b.empty()) sum += b.back() - '0', b.pop_back(); res.push_back((sum % 10) + '0'); sum /= 10; } reverse(res.begin(), res.end()); return res; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); string a, b;...
-
[BOJ] 1700 : 멀티탭 스케줄링
1700 : 멀티탭 스케줄링 풀이 가장 나중에 사용할 것 부터 뽑아주면 된당 코드 #include <stdio.h> #include <vector> using namespace std; int n, k, ans; int ord[101]; vector<int> tab; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < k; i++) { scanf("%d", &ord[i]); } for (int i = 0; i < k; i++) { int flag = 0; for (int t = 0; t < tab.size(); t++) { if (tab[t] ==...
-
[BOJ] 1476 : 날짜 계산
1476 : 날짜 계산 풀이 역시 중국인은 똑똑해!!! 코드 #include <stdio.h> int m, s, e, x; int main() { scanf("%d %d %d", &e, &s, &m); x = (e*6916+s*4845+m*4200)%7980; return ~printf("%d", x ? x : 7980); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 5543 : 상근날드
5543 : 상근날드 풀이 조아조아 코드 #include <stdio.h> #include <algorithm> int a, b, c, r, i = 2; int main() { while (i--) scanf("%d %d %d", &a, &b, &c), r += std::min({ a,b,c }); return ~printf("%d", r - 50); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[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] 1783 : 병든 나이트
1783 : 병든 나이트 풀이 깁잇투유마눈눈눈눈눈눈눈빛 쏟아지는마터터터터터터터터치 코드 #include <stdio.h> int n, m; int main() { scanf("%d %d", &n, &m); if (n == 1) puts("1"); else if (n == 2) { if (m <= 6) printf("%d", (m + 1) / 2); else puts("4"); } else { if (m <= 4) printf("%d", m); else if (m == 5 || m == 6) puts("4"); else printf("%d", m - 2); } return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 1410 : 패턴의 개수
1410 : 패턴의 개수 풀이 bitmask dp를 해보자! 근데 이거 풀이를 어떻게 써야하지 dp[len][bit] = 패턴의 길이를 len까지만 놓고 볼 때, 마스킹 된 패턴에만 일치하는 길이 len짜리 문자열의 수 코드 #include <iostream> #include <string> using namespace std; const int mod = 1000003; int n, k; int dp[50][1 << 15]; string str[15]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> k; for (int i = 0; i < n; i++) cin >> str[i]; int len...
-
[BOJ] 1051 : 숫자 정사각형
1051 : 숫자 정사각형 풀이 주위를 둘러보면 온통 네모난 것들 뿐인데~ 코드 #include <stdio.h> int n, m, k, i, j; char a[55][55]; int main() { scanf("%d %d", &n, &m); for (i = 0; i < n; i++) scanf("%s", a[i]); k = n < m ? n : m; while (k--) for (i = 0; i < n - k; i++) for (int j = 0; j < m - k; j++) if (a[i][j] == a[i][j+k]...
-
[BOJ] 1049 : 기타줄
1049 : 기타줄 풀이 단가 후려치기 ㄱㄱ 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int n, m, a = 1e9, b = 1e9, c, d; int main() { scanf("%d %d", &n, &m); while (m--) { scanf("%d %d", &c, &d); a = min(a, c); b = min(b, d); } a = min(a, b*6); printf("%d", n/6*a + min(a, (n%6)*b)); return 0; } 아무말 백준, 백준 온라인...
-
[BOJ] 9252 : LCS 2
9252 : LCS 2 풀이 http://codersbrunch.blogspot.kr/2016/12/9252-lcs-2.html 코드 #include <stdio.h> #include <algorithm> int dp[1234][1234]; char s1[1234], s2[1234]; void f(int i, int j) { if (!dp[i][j]) return; if (s1[i] == s2[j]) { f(i-1, j-1); putchar(s1[i]); } else dp[i-1][j] > dp[i][j-1] ? f(i-1, j) : f(i, j-1); } int main() { scanf("%s\n%s", s1 + 1, s2 + 1); int i, j; for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++) dp[i][j] = std::max({ dp[i-1][j], dp[i][j-1],...
-
[BOJ] 11000 : 강의실 배정
11000 : 강의실 배정 풀이 일반적으로 스위핑 해서 풀면 (start == end)인 경우를 처리하기가 까다롭다. pq를 이용해서 풀어주자. 코드 #include <stdio.h> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> pii; int n; pii p[200002]; priority_queue<pii> pq; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &p[i].first, &p[i].second); } sort(p, p + n); for (int i = 0; i < n; i++) { int s =...
-
[BOJ] 1449 : 수리공 항승
1449 : 수리공 항승 풀이 앞에서부터 순서대로 덮어주면 된다 파이프 터진 순서가 정렬되어 있다는 얘기가 없으니 정렬도 꼭 해주자 코드 #include <stdio.h> #include <algorithm> int n, l, a[1001]; int main() { scanf("%d %d", &n, &l); for (int i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a + n); int tmp = a[0], cnt = 1; for (int i = 0; i < n; i++) if (tmp + l - 1 < a[i]) tmp...
-
[BOJ] 4796 : 캠핑
4796 : 캠핑 풀이 룰루랄라 코드 #include <stdio.h> int a, b, c, d; int main() { while (1) { scanf("%d %d %d", &a, &b, &c); if (!a && !b && !c) break; printf("Case %d: %d\n", ++d, c/b*a + (c%b < a ? c%b : a)); } return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2503 : 숫자 야구
2503 : 숫자 야구 풀이 모든 숫자랑 모든 질문을 비교 해주자. 코드 #include <stdio.h> int n, ans, a[3], b[3]; struct ABC { int num, st, ba; } qry[101]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d %d", &qry[i].num, &qry[i].st, &qry[i].ba); } for (int i = 123; i <= 987; i++) { int cnt = 0; a[0] = i/100, a[1] = i/10%10, a[2] = i%10; if (!a[1]...
-
[BOJ] 10448 : 유레카 이론
10448 : 유레카 이론 풀이 1000 이하인 삼각수를 모두 구해보자! 그러한 (1000 이하인) 삼각수의 개수가 얼마 되지 않으므로 3중 for문 돌면서 완전탐색 해주면 된다! 코드 #include <stdio.h> #include <vector> using namespace std; int tc, n, ans; vector<int> v; int main() { for (int i = 1; i*(i+1)/2 <= 1000; i++) v.push_back(i*(i+1)/2); for (scanf("%d", &tc); tc--;) { scanf("%d", &n); ans = 0; for (int i : v) for (int j : v) for (int k :...
-
[BOJ] 3085 : 사탕 게임
3085 : 사탕 게임 풀이 맵의 크기가 50*50밖에 되지 않는다 (!) 인접한 칸을 swap하는 경우도 최대 50*49*2번밖에 되지 않는다 (!!) 모든 (x, y)를 돌면서 스왑 놀이를 해보자~! 코드 #include <stdio.h> #include <algorithm> using namespace std; const int dx[] = { 0,1 }; const int dy[] = { 1,0 }; int n, ans; char a[55][55]; int check() { int ret = 1, cnt = 1; for (int i = 1; i <= n; i++) { for...
-
[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] 1520 : 내리막 길
1520 : 내리막 길 풀이 메모이제이션 하면서 탐색해주자!! 코드 #include <stdio.h> const int dx[] = { 0,1,0,-1 }; const int dy[] = { 1,0,-1,0 }; int n, m, a[505][505], d[505][505]; int dfs(int x, int y) { if (x == n && y == m) return 1; if (~d[x][y]) return d[x][y]; d[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if...
-
[BOJ] 2668 : 숫자고르기
2668 : 숫자고르기 풀이 사이클을 찾아주면 된다! 우아하게 코드를 작성해보자. 코드 #include <stdio.h> int n, cnt, CNT[101], a[101]; int gogo(int now, int start) { for (int i = 1; i <= n; i++) { now = a[now]; if (now == start) return (cnt++, CNT[now]++); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= n; i++) gogo(i, i);...
-
[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] 2504 : 괄호의 값
2504 : 괄호의 값 풀이 뚜룹뚜빠라빠라 코드 #include <stdio.h> #include <stack> using namespace std; int sum, tmp = 1; char str[33]; stack<char> stk; int main() { scanf("%s", str + 1); for (int i = 1; str[i]; i++) { switch (str[i]) { case '(': btmp *= 2, stk.push('('); break; case '[': tmp *= 3, stk.push('['); break; case ')': if (str[i - 1] == '(') sum += tmp; if (stk.empty()) return !printf("0"); if (stk.top() == '(') stk.pop();...
-
[BOJ] 2530 : 인공지능 시계
2530 : 인공지능 시계 풀이 오.바.와.치 코드 #include <stdio.h> int main() { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d); c += d; b += c / 60, c %= 60; a += b / 60, b %= 60; a %= 24; printf("%d %d %d", a, b, c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제,...
-
[BOJ] 2460 : 지능형 기차
2460 : 지능형 기차 풀이 이보게 풀이를 찾아온 자네! 입력을 어떻게 받을지 고민하는 표정이군. scanf는 입력 파일의 끝을 만나면 End Of File (EOF)를 리턴한다네. 그리고 EOF는 대부분의 컴파일러에서 상수값 -1로 정의되어있지! (컴파일러 마다 다르게 동작할 수도 있네만) 대부분의 환경에서 -1은 int형에서 111..111(2)로 저장된다네. (부호 비트가 1로 켜지는 셈이지!) 자세한 것은 위키피디아를 참고하게나. 따라서 111...111(2)를 ~ 연산자로 비트반전 시켜주면 0이 된다네! 그러므로 EOF를 만나면 while (0)이 되어 반복문이 종료되는 것이지! 하지만 바람직한 풀이는 while (scanf() !=...
-
[BOJ] 1676 : 팩토리얼 0의 개수
1676 : 팩토리얼 0의 개수 풀이 2랑 5의 개수를 세어주면 되는데 어차피 5의 개수가 2의 개수보다 항상 적기 때문에 5의 개수만 세어주어도 된다. 코드 #include <stdio.h> int n, c; int main() { scanf("%d", &n); while (n) n /= 5, c += n; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2075 : N번째 큰 수
2075 : N번째 큰 수 풀이 음 뭔가 풀이가 로또 뽑는 거 같군 코드 #include <stdio.h> #include <queue> using namespace std; int n; priority_queue<int> pq; int main() { scanf("%d", &n); for (int a, i = 0; i < n*n; i++) { scanf("%d", &a); pq.push(-a); if (pq.size() > n) pq.pop(); } printf("%d", -pq.top()); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제...
-
[BOJ] 1947 : 선물 전달
1947 : 선물 전달 풀이 오랜만에 정상적인 풀이!! 더 자세히 알고 싶다면 구글에 완전순열 또는 교란을 검색해 보자! 증명 D[n] = (n-1) * (D[n-1] + D[n-2]) 자연수 1~n에 n+1을 더해서 완전순열을 만들어 보자. n+1은 1~n 중의 어떤 수 k의 자리에 놓인다. 이러한 k는 1부터 n까지 총 n개가 있을 수 있다. 그리고 우리는 이후의 상황을 다음의 두 경우로 나눌 수 있다. 1. n+1이 k의 자리에, k가 n+1의 자리에 놓이는 경우: k와 n+1을 제외한 나머지 n-1개의 수로...
-
[BOJ] 1547 : 공
1547 : 공 풀이 자자~ 돈 놓고 돈 먹기~ 코드 #include <stdio.h> #include <algorithm> int n, x, y, a[4] = { 0,1 }; int main() { scanf("%d", &n); while (n--) scanf("%d %d", &x, &y), std::swap(a[x], a[y]); for (n = 1; n <= 3; n++) if (a[n]) printf("%d", n); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1159 : 농구 경기
1159 : 농구 경기 풀이 사실 그냥 체킹 배열에 카운트 해줘도 되는데 map 안 쓴지가 오래돼서 써봤다 ㅎㅎ 코드 #include <cstdio> #include <map> using namespace std; int n; char a[155]; map<char, int> s; int main() { scanf("%d", &n); while (n--) scanf("%s", a), s[a[0]]++; for (auto it : s) if (it.second >= 5) putchar(it.first), n++; if (n == -1) printf("%s", "PREDAJA"); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨,...
-
[BOJ] 1057 : 토너먼트
1057 : 토너먼트 풀이 My life for Aiur! 코드 #include <stdio.h> int n, a, b, c; int main() { scanf("%d %d %d", &n, &a, &b); while (a != b) a = a/2+a%2, b = b/2+b%2, c++; printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1764 : 듣보잡
1764 : 듣보잡 풀이 stl로 떡칠해보자!! 코드 #include <iostream> #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; int n, m; string t; set<string> s; vector<string> v; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; while (n--) cin >> t, s.insert(t); while (m--) cin >> t, s.count(t) ? v.emplace_back(t) : [](){}(); sort(v.begin(), v.end()); cout << v.size() << "\n"; for (auto it : v) cout << it << "\n"; return 0; }...
-
[BOJ] 1991 : 트리 순회
1991 : 트리 순회 풀이 아 퇴사하고싶다 코드 #include <stdio.h> #define p(c) putchar(c); int n, i; char a, b, c, t[99][2]; void f(int x) { if (i == 0) p(x); if (t[x][0] != '.') f(t[x][0]); if (i == 1) p(x); if (t[x][1] != '.') f(t[x][1]); if (i == 2) p(x); } int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf(" %c %c %c", &a, &b, &c); t[a][0] = b,...
-
[BOJ] 2941 : 크로아티아 알파벳
2941 : 크로아티아 알파벳 풀이 쿵짝쿵짝 쿵짜라 코드 #include <stdio.h> #include <string.h> int i, c; char s[111]; int main() { scanf("%s", s); while (i < strlen(s)) { if (s[i] == 'c' && (s[i+1] == '=' || s[i+1] == '-')) i++; else if (s[i] == 'd') { if (s[i+1] == '-') i++; else if (s[i+1] == 'z' && s[i+2] == '=') i+=2; } else if ((s[i] == 'l' || s[i] == 'n') && s[i+1] == 'j')...
-
[BOJ] 2775 : 부녀회장이 될테야
2775 : 부녀회장이 될테야 풀이 점화식을 오지게 세워보자~ d[i][j] = i층 j호에 사는 사람의 수 d[i][j] = d[i-1][j] + d[i][j-1] 코드 #include <stdio.h> int t, n, k, d[15][15]; int main() { for (int i = 1; i < 15; i++) d[0][i] = i; for (int i = 1; i < 15; i++) for (int j = 1; j < 15; j++) d[i][j] = d[i-1][j] + d[i][j-1]; scanf("%d", &t); while (t--) { scanf("%d %d", &k, &n);...
-
[BOJ] 2042 : 구간 합 구하기
2042 : 구간 합 구하기 풀이 세그트리를 짜보자~ 코드 #include <iostream> using namespace std; typedef long long ll; const int n_ = 1048576 + 1; int n, m, k, arr[n_]; ll tree[n_ * 2]; ll init(int now, int lft, int rgt) { if (lft == rgt) return tree[now] = arr[lft]; return tree[now] = init(now * 2, lft, (lft + rgt) / 2) + init(now * 2 + 1, (lft + rgt) / 2 + 1,...
-
[BOJ] 2953 : 나는 요리사다
2953 : 나는 요리사다 풀이 아 출근하기 싫다 코드 i = 5, j, a, s, mn, mx; main() { while (i--) { for (j = 0, s = 0; j < 4; j++) scanf("%d", &a), s += a; if (mx < s) mn = 5 - i, mx = s; } printf("%d %d", mn, mx); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제,...
-
[BOJ] 1966 : 프린터 큐
1966 : 프린터 큐 풀이 프린터 터져욧!! 코드 #include </bits/stdc++.h> using namespace std; int main() { int tc; scanf("%d", &tc); while (tc--) { int n, m, cnt = 1; queue<pair<int, int> > qu; priority_queue<int> pq; scanf("%d %d", &n, &m); for (int i = 0, a; i < n; i++) { scanf("%d", &a); qu.push({ a,i }); pq.push(a); } while (!pq.empty()) { auto n1 = qu.front(); int n2 = pq.top(); if (n1.first == n2) { if (n1.second...
-
[BOJ] 2309 : 일곱 난쟁이
2309 : 일곱 난쟁이 풀이 돌려돌려~ 코드 #include <stdio.h> #include <algorithm> int a[10]; int main() { for (int i = 0; i < 9; i++) scanf("%d", &a[i]); std::sort(a, a + 9); for (int i = 0; i < (1 << 9); i++) { int cnt = 0, sum = 0; for (int j = 0; j < 9; j++) if ((1 << j) & i) cnt++, sum += a[j]; if (cnt != 7 || sum...
-
[BOJ] 11722 : 가장 긴 감소하는 부분 수열
11722 : 가장 긴 감소하는 부분 수열 풀이 죽을 것 같아도 미칠 것 같아도 하늘만 뚫어지게 보며 버텼죠 그대를 본다면 눈물을 본다면 분명 난 주저앉고 말테니 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, tmp, len, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &tmp); auto ret = lower_bound(a, a + i, tmp, [](const int &i, const int &j) { return i >...
-
[BOJ] 6603 : 로또
6603 : 로또 풀이 그댈 그린 밤들이 내게 욕심이란 걸 맘 아프게 알아 나를 택한 운명이 행여 그댈 맴돌아 붙잡지 못하게 이제 그대 곁에서 떠나가 코드 #include <stdio.h> int k, s[51], a[7]; void dfs(int len, int cnt) { if (cnt == 6) { for (int i = 1; i <= 6; i++) printf("%d ", a[i]); puts(""); return; } if (len >= k) return; a[cnt + 1] = s[len + 1]; dfs(len + 1, cnt +...
-
[BOJ] 1182 : 부분집합의 합
1182 : 부분집합의 합 풀이 완전탐색! dfs로 짜도 되고 n이 작으니까 비트마스킹 해도 된다. 코드 #include <stdio.h> int n, s, ans, a[21]; int main() { scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 1; i < (1 << n); i++) { int sum = 0; for (int j = 0; j < n; j++) if (i & (1 << j)) sum += a[j]; ans...
-
[BOJ] 5585 : 거스름돈
5585 : 거스름돈 풀이 천 번을 내게 물어봐도 사랑은 그대 하나 깊은 후회 속에 살겠죠 잘못한 일이 왜 이렇게 많은지 평생 그댈 향해서 죄를 빌게요 코드 #include <stdio.h> int n, s, i = 6, a[6] = { 1, 5, 10, 50, 100, 500 }; int main() { scanf("%d", &n); n = 1000 - n; while (i--) while (n >= a[i]) n -= a[i], s++; printf("%d", s); return 0; } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 2875 : 대회 or 인턴
2875 : 대회 or 인턴 풀이 http://codersbrunch.blogspot.kr/2016/09/2875-or.html 코드 #include <stdio.h> #include <algorithm> int n, m, k; int main() { scanf("%d %d %d", &n, &m, &k); printf("%d", std::min({ n/2, m, (n+m-k)/3 })); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 10610 : 30
10610 : 30 풀이 어떤 숫자 N이 3의 배수인 조건 : 모든 자리에 있는 숫자들의 합이 3의 배수 10의 배수인 조건 : 첫째 자리의 숫자가 0 이 둘을 합쳐주면 30인 조건이 된다 (!!!) 코드 #include <stdio.h> int i, sum, cnt[10]; char str[100002]; int main() { scanf("%s", str); for (i = 0; str[i]; i++) cnt[str[i] - '0']++, sum += str[i] - '0'; if (!cnt[0] || sum % 3) return ~printf("-1"); for (i = 9; i >=...
-
[BOJ] 11725 : 트리의 부모 찾기
11725 : 트리의 부모 찾기 풀이 별 하나에 추억과 별 하나에 사랑과 별 하나에 쓸쓸함과 별 하나에 동경(憧憬)과 별 하나에 시와 별 하나에 어머니, 어머니 코드 #include <stdio.h> #include <vector> using namespace std; int n, pnt[100001]; vector<int> gph[100001]; void dfs(int now) { for (int nxt : gph[now]) if (pnt[now] ^ nxt) pnt[nxt] = now, dfs(nxt); } int main() { scanf("%d", &n); for (int i = 0, u, v; i < n - 1; i++) {...
-
[BOJ] 1068 : 트리
1068 : 트리 풀이 리프 노드라는 것은, 들어오는 간선이 없다는 것. 코드 #include <stdio.h> int n, i, now, del, cnt, gph[51], idg[51]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &gph[i]); if (~gph[i]) idg[gph[i]]++; } scanf("%d", &del); if (gph[del] == -1) return ~printf("0"); idg[gph[del]]--; for (i = 0; i < n; i++) { if (idg[i]) continue; cnt++; for (now = i; ~now; now = gph[now]) if (now ==...
-
[BOJ] 1967 : 트리의 지름
1967 : 트리의 지름 풀이 트리에서 임의의 노드 ㄱ을 고른 뒤 ㄱ에서 가장 먼 노드 ㄴ을 찾고 ㄴ에서 가장 먼 노드 ㄷ을 찾으면 ㄴ과 ㄷ이 트리의 지름이 된다 (!) 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 4; struct edg { int idx, dst; }; int n, abc, sum; vector<edg> gph[n_]; void dfs(int prv, int now, int dst) { if (sum < dst) sum = dst, abc...
-
[BOJ] 1562 : 계단 수
1562 : 계단 수 풀이 D[length][number][bitmask] = D[length - 1][number ± 1][bitmask | (1 << number)] 룰루랄라 코딩을 해보자~ 코드 #include <stdio.h> #include <string.h> const int mod = 1e9; int n, ans, dp[101][10][1025]; int dfs(int len, int num, int msk) { int &ret = dp[len][num][msk]; msk |= (1 << num); if (num < 0 || num > 9) return 0; if (len == n) return (msk == (1 << 10) - 1) ? 1 :...
-
[BOJ] 1693 : 트리 색칠하기
1693 : 트리 색칠하기 풀이 http://codersbrunch.blogspot.kr/2017/07/1693.html 읽고 구현한 코드입니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e5 + 5; int n, dp[n_][18]; vector<int> gph[n_]; void dfs(int prv, int now) { dp[now][0] = 2e9; for (int col = 1; col <= 17; col++) dp[now][col] += col; for (int nxt : gph[now]) { if (nxt == prv) continue; dfs(now, nxt); int fst = 0, snd = 0; for (int col...
-
[BOJ] 2798 : 블랙잭
2798 : 블랙잭 풀이 퇴근 하고 싶다 코드 #include <stdio.h> int n, m, i, j, k, a[101], ans; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (i = 0; i < n; i++) for (j = 0; j < n; j++) for (k = 0; k < n; k++) if (i != j && j != k && k != i) { int t...
-
[BOJ] 1727 : 커플 만들기
1727 : 커플 만들기 풀이 D[n][m] = 오름차순으로 남자 n명, 여자 m명을 짝짓는 최소의 값 D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n-1][m]) (if n > m) D[n][m] = min(D[n-1][m-1] + abs(man[n] - woman[m]), D[n][m-1]) (if n < m) 코드 #include <stdio.h> #include <algorithm> using namespace std; int abs(int a) { return a < 0 ? -a : a; } int n, m, a[1001], b[1001], d[1001][1001]; int main() { scanf("%d %d", &n, &m); for (int...
-
[BOJ] 11724 : 연결 요소의 개수
11724 : 연결 요소의 개수 풀이 느낌있게 깊이우선탐색 코드 #include <iostream> #include <vector> using namespace std; int n, m, ans, vst[1001]; vector<int> gph[1001]; void dfs(int now) { vst[now] = 1; for (int nxt : gph[now]) if (!vst[nxt]) dfs(nxt); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; for (int i = 0, u, v; i < m; i++) { cin >> u >> v; gph[u].push_back(v), gph[v].push_back(u); } for (int i = 1; i <=...
-
[BOJ] 11004 : K번째 수
11004 : K번째 수 풀이 원래는 퀵소트를 응용한 퀵서치(?) 뭐 그런 걸로 짜야한다는데 귀찮아서 레퍼런스를 뒤져보니 엄청난 물건을 찾아냈다 (!!) 코드 #include <iostream> #include <algorithm> using namespace std; int n, k, a[5000005]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; nth_element(a, a + k - 1, a + n); cout << a[k - 1]; return 0; } 아무말 백준, 백준 온라인 저지,...
-
[BOJ] 2525 : 오븐 시계
2525 : 오븐 시계 풀이 나눗셈을 오지고 지리게 해보자. 코드 #include <stdio.h> int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); b += c, a += b / 60; b %= 60, a %= 24; printf("%d %d", a, b); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2522 : 별찍기 - 12
2522 : 별찍기 - 12 풀이 오늘도 별이 바람에 스치운다 코드 #include <cstdio> int abs(int a) { return a < 0 ? -a : a; } int main() { int n, i, j, k; scanf("%d", &n); for (i = 1; i < n * 2; i++) { for (j = 0; j < abs(n - i); j++) printf(" "); for (k = 0; k < n - j; k++) printf("*"); puts(""); } return 0; }...
-
[BOJ] 2581 : 소수
2581 : 소수 풀이 소수를 멋지게 구해보자. 코드 #include <stdio.h> int n, m, sum, min; void f(int k) { if (k == 1) return; for (int i = 2; i <= k / 2; i++) if (k % i == 0) return; if (!min) min = k; sum += k; } int main() { scanf("%d %d", &n, &m); for (int i = n; i <= m; i++) f(i); if (!sum) printf("-1"); else printf("%d\n%d", sum, min);...
-
[BOJ] 1158 : 조세퍼스 문제
1158 : 조세퍼스 문제 풀이 단순 구현 코드 #include <bits/stdc++.h> using namespace std; int n, m, pos; vector<int> a; int main() { cin >> n >> m; for (int i = 0; i < n; i++) a.push_back(i + 1); printf("<"); while (1) { pos = (pos + m - 1) % a.size(); if (a.size() > 1) { printf("%d, ", a[pos]); } else { printf("%d>", a[pos]); break; } a.erase(a.begin() + pos); } return 0; } 아무말...
-
[BOJ] 1005 : ACM Craft
1005 : ACM Craft 풀이 위상딱 위상딱 신나는 노래 나도 한 번 불러본다~ 코드 #include <iostream> #include <string.h> #include <vector> using namespace std; const int n_ = 1e3 + 3; int req[n_], dst[n_], idg[n_], ans[n_]; vector<int> gph[n_]; void dfs(int now) { idg[now]--; for (int nxt : gph[now]) { ans[nxt] = max(ans[nxt], ans[now] + req[nxt]); if (!(--idg[nxt])) dfs(nxt); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc; cin >> tc; while (tc--) { int n, k, w;...
-
[BOJ] 2468 : 안전 영역
2468 : 안전 영역 풀이 DFS를 멋있게 폼나게 오지게 간지나게 돌려보자. 코드 #include <stdio.h> #include <string.h> const int dx[] = { 0,0,1,-1 }; const int dy[] = { 1,-1,0,0 }; int n, w, cnt, ans, mx, a[102][102], b[102][102]; inline int max(int a, int b) { return a > b ? a : b; } void dfs(int x, int y) { b[x][y] = 0; for (int i = 0; i < 4; i++) { int nx...
-
[BOJ] 8902 : 색상의 길이
8902 : 색상의 길이 풀이 잘 정리된 풀이가 있어서 풀이와 출처를 첨부합니다! 목적 함수 : Sum { Length(color) } Length(c) = LastIdx(c) - FirstIdx(c) + 1 이므로 결국, Sum { LastIdx } + Sum { -FirstIdx }를 최소화 시키는 문제로 볼 수 있다. 2개의 차 행렬은 앞에서부터 순차적으로 합쳐지기 때문에 첫 번째 차 행렬에서 i개의 차량이 합쳐지고, 두 번째 차 행렬에서 j개의 차량이 합쳐졌을 때를 상태 공간으로 삼아 동적계획법을 수행할 수 있다. 이를 D[i][j]라고 하자....
-
[BOJ] 13458 : 시험 감독
13458 : 시험 감독 풀이 행복을 줄 수 없었어 그런데 사랑을 했어 네 곁에 감히 머무른 내 욕심을 용서치마 코드 #include <stdio.h> int n, i, a[1000001], b, c; long long ans; int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", a + i); scanf("%d %d", &b, &c); for (i = 0; i < n; i++) { ans++, a[i] -= b; if (a[i] > 0) ans += a[i] / c +...
-
[BOJ] 13460 : 째로탈출 2
13460 : 째로탈출 2 풀이 늘 그랬었어 넌 참 예뻤어 말 할 때마다 웃는 눈도 내가 아니어도 누군가 사랑해 줄 사람 많을 거야 코드 #include <stdio.h> #include <queue> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; struct ABC { int cnt, rx, ry, bx, by; }; queue<ABC> que; int n, m, rx, ry, bx, by; bool chk[11][11][11][11]; char toy[12][12]; int main() { scanf("%d %d\n", &n, &m);...
-
[BOJ] 14888 : 연산자 끼워넣기
14888 : 연산자 끼워넣기 풀이 완전탐색 완전탐색 신나는 노래~ 코드 #include <stdio.h> int n, i, mn = 2e9, mx = -2e9, a[11], op[4]; void dfs(int c, int v) { if (c == n) { mn = mn < v ? mn : v; mx = mx > v ? mx : v; return; } if (op[0]) --op[0], dfs(c + 1, v + a[c]), ++op[0]; if (op[1]) --op[1], dfs(c + 1, v - a[c]), ++op[1]; if...
-
[BOJ] 3190 : 뱀
3190 : 뱀 풀이 매번 늦어도 이해할게 누굴 만났니 먼저 묻지 않을게 고집스런 내 사랑 너의 말은 변명이라도 믿고 싶을테니 눈 비비는 척 눈물 닦아내고 다음 약속도 잡을 이유 만들지 네 마음보다 한숨과 친해져도 널 보기위해 난 사니까 수 없이 어긋난대도 기다릴게 아무리 가슴 아파도 웃어볼게 떠나선 안 돼 서둘러 져버리지 마 날 밀어내도 깊어지는 이 사랑을 봐 내 입을 막아도 세상이 다 아는데 왜 너만 몰라 왜 널 지킬 남자를 몰라 코드 #include <stdio.h>...
-
[BOJ] 14504 : 로봇 청소기
14504 : 로봇 청소기 풀이 문제에서 주어진대로 구현하면 된다. 지문이 좀 헷갈리게 써있어서 많이 헤메다 풀었다 ㅠㅠ 코드 #include <stdio.h> #define r(a,b) a=(a+b)%4 const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,1,0,-1 }; int n, m, x, y, nx, ny, d, ans; int main() { int a[55][55] = { 0 }; scanf("%d %d %d %d %d", &n, &m, &x, &y, &d); for (int i = 0; i < n; i++) for...
-
[BOJ] 10875 : 뱀
10875 : 뱀 풀이 삼성 문제들은 하나같이 빡친다 단순 구현! 인데 좀 빡치는 구현 O(n^2)에 풀어주자. i번째에 뱀이 움직여서 생긴 선분과 1 ~ i-1번째까지 움직여서 생긴 선분들을 비교해주면 된다. check() 함수가 교차에 관한 구현을 담고 있다. 맵 밖으로 나가는지 여부는 귀찮으니 맵 바깥에 선분을 그어 한 번에 처리해버리자. 음… 자세한 건 주석을 참조하자. 코드 #include <stdio.h> #include <vector> #include <algorithm> #define pb push_back using namespace std; const int INF = 2e9; const int dx[] =...
-
[BOJ] 1213 : 팰린드롬 만들기
1213 : 팰린드롬 만들기 풀이 앞뒤로 앞뒤로 넣어주자~ 코드 #include <stdio.h> #include <string.h> int n, i, cnt, flag, a[26]; char str[55]; int main() { scanf("%s", str); n = strlen(str); for (i = 0; i < n; i++) { a[str[i] - 65]++; } for (i = 0; i < 26; i++) { while (a[i]) { if (a[i] == 1) { if (flag) { puts("I'm Sorry Hansoo"); return 0; } flag = 1, str[n / 2] =...
-
[BOJ] 1018 : 체스판 다시 칠하기
1018 : 체스판 다시 칠하기 풀이 그냥 다 돌려보면 된다. 코드 #include <stdio.h> #define min(a,b) (a)<(b)?(a):(b) int n, m, i, j, a, b, ans = 1e9; char str[55][55]; int main() { scanf("%d %d", &n, &m); for (i = 0; i < n; i++) scanf("%s", str[i]); for (i = 0; i < n - 7; i++) for (j = 0; j < m - 7; j++) { int cnt = 0; for (a = i; a...
-
[BOJ] 1450 : 냅색문제
1450 : 냅색문제 풀이 숫자의 크기가 너무 커서 일반적인 냅색 풀이로는 풀 수 없다. 그렇다고 2^30을 돌리자니 그것도 크기가 너무 크다. 수열을 정렬하고 반으로 나눠서 절반씩 완전탐색 해주자. 2^15씩 두 번이니 충분히 돌고도 남는다. 그리고 완전탐색한 두 조합을 linear하게 잘 섞어주자. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int n, c, ans, a[33]; vector<int> v1, v2; void dfs(int s, int e, int sum, vector<int>& v) { if (sum > c) return; if...
-
[BOJ] 1799 : 비숍
1799 : 비숍 풀이 일반적인 풀이로 답을 구하려면 O(2^(10*10))으로 TLE가 난다. 체스판에서 대각선이 흑과 백으로 구분됨을 이용하자. 흑색칸 O(2^(5*5))와 백색칸 O(2^(5*5))를 따로 구해서 더하면 TLE를 피할 수 있다. 앞선 (boj 9663 N-Queen) 풀이에서 언급한 x를 +로 뒤집기(?)를 이용할 수 있겠다. 코드 #include <stdio.h> #define max(a,b) (a)>(b)?(a):(b) int n, f, ans[2], l[33], r[33], a[33][33]; void dfs(int x, int y, int c) { ans[f] = max(ans[f], c); if (y >= n) y = f ^ (++x %...
-
[BOJ] 9663 : N-Queen
9663 : N-Queen 풀이 룰루랄라 백트래킹을 해주자~ x 모양 대각선을 + 모양으로 뒤집어서 생각할 때 (x, y) -> (x+y, x-y)를 이용하면 편하다. 말이 조금 이상하지만 아무튼 저렇게 넣고 출력해보면 대강 이해 갈 것이다. https://www.acmicpc.net/problem/2496 위 문제도 이 테크닉을 써서 풀 수 있겠다. 코드 #include <stdio.h> int n, ans, u[33], l[33], r[33]; void dfs(int h, int c) { if (c == n) { ans++; return; } for (int i = 0; i < n; i++) {...
-
[BOJ] 1064 : 평행사변형
1064 : 평행사변형 풀이 hypot(a, b)는 a와 b를 높이, 너비로 하는 빗변의 길이를 구해주는 함수이다. 평행사변형이 만들어질 수 없는 경우를 찾아보자. 둘 이상의 점이 겹치거나, 세 점이 한 직선 위에 있으면 (= 기울기가 같으면) 사각형이 될 수 없다. ccw에서 기울기를 구하는 식을 가져다 쓰자! 여기에 개꿀개꿀 공식이 써있으니 참고하자! 둘 이상의 점이 겹치는 경우도 한 직선 위에 있는 경우이므로 별개로 처리해줄 필요는 없다. (개꿀!) 이제 평행사변형의 둘레의 길이를 찾아보자. 먼저, 남아있는 하나의 점을 찾을 필요가...
-
[BOJ] 13269 : 쌓기나무
13269 : 쌓기나무 풀이 앞에서 보이는 최대 값들로 채워준 다음 옆에서 보이는 최대 값들을 만족하게 바꿔준다 그리고 조건을 만족하는지 체크해보자! 코드 #include <stdio.h> #define REP(k,n) for(k=0;k<n;k++) #define RRP(k,n) for(k=n-1;k>=0;k--) int main() { int n, m, i, j, a[500][500], b[500], c[500]; scanf("%d %d", &n, &m); REP(i,n) REP(j,m) scanf("%d", &a[i][j]); REP(j,m) { scanf("%d", &b[j]); REP(i,n) if (a[i][j] == 1) a[i][j] = b[j]; } RRP(i,n) { scanf("%d", &c[i]); REP(j,m) if (a[i][j] > c[i]) a[i][j] = c[i]; } REP(j,m)...
-
[BOJ] 13268 : 셔틀런
13268 : 셔틀런 풀이 달빛이 흡사 비오듯 쏟아지는 밤에도 우리는 헐어진 성(城)터를 헤매이면서 언제 참으로 그 언제 우리 하늘에 오롯한 태양을 모시겠느냐고 가슴을 쥐어뜯으며 이야기하며 이야기하며 가슴을 쥐어뜯지 않았느냐? 코드 #include <stdio.h> #include <stdlib.h> #define a(e) for(int i=1;i<=e;i++)n-=5,f(i) #define b(e) for(int i=e;i>=1;i--)n-=5,f(i) int n, k; void f(int a) { if (n <= 0) { printf("%d", a); exit(0); } } int main() { scanf("%d", &n); n %= 100; for (int j = 0; j <= 4;...
-
[BOJ] 13560 : 축구게임
13560 : 축구게임 풀이 랑주의 정리! S[i] = a[1~i]의 합, S[1~k] >= kC2 S[n] = nC2 증명 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, s = 0, a[10000]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); std::sort(a, a + n); for (i = 0; i < n; i++) { s += a[i]; if (s < (i+1)*i/2) return ~printf("-1"); } printf("%d", s == n*(n-1)/2 ? 1 : -1);...
-
[BOJ] 1987 : 알파벳
1987 : 알파벳 풀이 마음도 한자리 못 앉아 있는 마음일 때, 친구의 서러운 사랑 이야기를 가을 햇볕으로나 동무 삼아 따라가면, 어느새 등성이에 이르러 눈물나고나. 코드 #include <cstdio> const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 }; int n, m, k, ch[99]; char s[22][22]; void dfs(int x, int y, int c) { if (k < c) k = c; if (k > 25) return; ch[s[x][y]] = 1; for (int i = 0; i...
-
[BOJ] 2580 : 스도쿠
2580 : 스도쿠 풀이 태양을 의논하는 거룩한 이야기는 항상 태양을 등진 곳에서만 비롯하였다. 코드 #include <stdio.h> #include <stdlib.h> #include <vector> using namespace std; struct ABC { int x, y, z; }; int a[9][9], x[9], y[9], z[9]; vector<ABC> p; void dfs(int now) { if (now == p.size()) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) printf("%d ", a[i][j]); puts(""); } exit(0); } int nx...
-
[BOJ] 14732 : 행사장 대여
14732 : 행사장 대여 풀이 오늘도 별이 바람에 스치운다. 코드 #include <stdio.h> int n, i, j, a, b, c, d, ans; bool chk[501][501]; int main() { for (scanf("%d", &n); n--;) { scanf("%d %d %d %d", &a, &b, &c, &d); for (i = a; i < c; i++) for (j = b; j < d; j++) if (!chk[i][j]) ans++, chk[i][j] = 1; } printf("%d", ans); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online...
-
[BOJ] 14731 : 謎紛芥索紀 (Large)
14731 : 謎紛芥索紀 (Large) 풀이 지수가 몹시 크다! 하지만 f`(2)라고 하지 않았던가! 2의 제곱꼴이란 뜻이다! 숫자를 제곱제곱제곱제곱 하면서 1000000000를 log로 줄이자! 나머지 연산에 주의하자! 코드 #include <stdio.h> const int mod = 1e9 + 7; int n; long long s, e, x; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &e, &x); long long t = 1, p = 2, q = x - 1; while (q)...
-
[BOJ] 14730 : 謎紛芥索紀 (Small)
14730 : 謎紛芥索紀 (Small) 풀이 잎새에 이는 바람에도 난 괴로워했다. 코드 n, s, e, x; main() { scanf("%d", &n); while (n--) scanf("%d %d", &e, &x), s+=e*x; printf("%d", s); } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 14729 : 칠무해
14729 : 칠무해 풀이 제한이 몹시 크다! 정렬하면 큰일난다! 대신, 소수점에 1000을 곱해서 정수 a로 만들어 준 다음에 카운팅 배열 cnt[a]에 체크해주자. 그래봤자 10만개이므로 cnt[0]부터 cnt[100000]까지 돌면 깔끔하게 풀 수 있다. 코드 #include <stdio.h> int n, a[100001], x, y; int main() { scanf("%d", &n); while (n--) { scanf("%d.%d", &x, &y); a[x*1000+y]++; } for (int i = 0, c = 0; i <= 100000; i++) { while (a[i]) { --a[i], ++c; printf("%d.%03d\n", i / 1000, i...
-
[BOJ] 14728 : 벼락치기
14728 : 벼락치기 풀이 띠용 이거 누가봐도 냅색인걸?! 코드 #include <stdio.h> #define max(a,b) (a)>(b)?(a):(b) int n, t, k, s, d[10001]; int main() { scanf("%d %d", &n, &t); while (n--) { scanf("%d %d", &k, &s); for (int i = t; i >= k; i--) d[i] = max(d[i], d[i - k] + s); } printf("%d", d[t]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge
-
[BOJ] 14727 : 퍼즐 자르기
14727 : 퍼즐 자르기 풀이 분할정복 + 세그트리로 푸는 풀이도 있다. 근데 복잡하다. 그리디하게 생각해보자. 순차적으로 돌면서 현재 막대의 높이가 이전 막대보다 작아졌다면 이전 막대는 현재 막대 이후로 고려할 필요가 없어진다. 넓이를 구해보자. 코드 #include <stdio.h> #include <stack> #include <algorithm> using namespace std; typedef long long ll; struct ABC { int idx, hgt; }; int n, h; ll ans; stack<ABC> stk; int main() { scanf("%d", &n); for (int i = 0; i < n; i++)...
-
[BOJ] 14726 : 신용카드 판별
14726 : 신용카드 판별 풀이 죽는 날까지 하늘을 우러러 한 점 부끄럼 없기를 코드 #include <stdio.h> int main() { int t; for (scanf("%d", &t); t--;) { int sum = 0; for (int i = 0, a; i < 16; i++) { scanf("%1d", &a); if (!(i % 2)) a *= 2; sum += a / 10 + a % 10; } if (sum % 10) puts("F"); else puts("T"); } return 0; } 아무말 백준, 백준 온라인...
-
[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] 1874 : 스택 수열
1874 : 스택 수열 풀이 스택에 차곡차곡 쌓다가 알맞은 숫자를 만나면 팝팝 해주자! 코드 #include <stdio.h> #include <stack> #include <vector> using namespace std; int n, a[100001]; stack<int> stk; vector<char> ans; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int pos = 0; for (int i = 1; i <= n; i++) { stk.push(i), ans.push_back('+'); while (!stk.empty() && stk.top() == a[pos]) { pos++, stk.pop(), ans.push_back('-'); } } if...
-
[BOJ] 5622 : 다이얼
5622 : 다이얼 풀이 따르릉 따르릉 비켜나세요~ 코드 #include <stdio.h> int s[27] = { 3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10 }; int main() { for (char c; ~scanf("%c", &c);) s[26] += s[c - 'A']; printf("%d", s[26]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 2490 : 윷놀이
2490 : 윷놀이 풀이 풍성한 한가위 되세요~ 코드 #include <stdio.h> int main() { for (int i = 0; i < 3; i++) { int s = 0, a; for (int j = 0; j < 4; j++) scanf("%d", &a), s += a; switch (s) { case 0: puts("D"); break; case 1: puts("C"); break; case 2: puts("B"); break; case 3: puts("A"); break; case 4: puts("E"); } } return 0; } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 2292 : 벌집
2292 : 벌집 풀이 a[i]를 중앙에서 i번째로 떨어진 껍데기를 이루는 육각형의 수라고 두면 a[i] = a[i-1] + 6 (a[0] = 1, a[1] = 6)이라는 식이 나온다. 이제 구현해보자! 룰루랄라 코드 #include <stdio.h> int main() { int n, i; scanf("%d", &n); n--; while (1) { n -= i*6, i++; if (n <= 0) break; } printf("%d", i); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바,...
-
[BOJ] 1016 : 제곱 ㄴㄴ 수
1016 : 제곱 ㄴㄴ 수 풀이 제곱 ㄴㄴ 수를 직접 세어주려면 시간이 너무 오래 걸린다. 제곱 ㄴㄴ 수를 제외한 나머지는 모두 제곱 ㅇㅇ 수(?)이므로 제곱 ㅇㅇ 수(?)를 카운팅해서 전체 개수에서 빼주자! 룰루랄라 코드 #include <stdio.h> typedef long long ll; bool chk[1000001], aux[1000001]; int main() { ll a, b; scanf("%lld %lld", &a, &b); int ans = b - a + 1; for (ll i = 2; i*i <= b; i++) { if (aux[i]) continue; for (ll...
-
[BOJ] 1977 : 완전제곱수
1977 : 완전제곱수 풀이 음 잘 세어주면 된다 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int a, b, sm, mn = (int)1e9; int main() { scanf("%d %d", &a, &b); for (int i = 1; i*i <= b; i++) { if (i*i >= a && i*i <= b) { mn = min(mn, i*i); sm += i*i; } } if (!sm) printf("-1"); else printf("%d\n%d", sm, mn);...
-
[BOJ] 1076 : 저항
1076 : 저항 풀이 잘 계산해주자 꺄르륵 코드 #include <iostream> #include <string> using namespace std; int i, j; long long sum; string a, b, c, s[] = {"black","brown","red","orange","yellow","green","blue","violet","grey","white" }; int main() { cin >> a >> b >> c; for (i = 0; i < 10; i++) { if (a == s[i]) sum += i * 10; if (b == s[i]) sum += i; } for (i = 0; i < 10; i++) if (c...
-
[BOJ] 1475 : 방 번호
1475 : 방 번호 풀이 6과 9는 구분없이 사용 가능하므로 그것만 신경써서 카운팅 해주면 된다 코드 #include <stdio.h> #include <string.h> #define max(a,b) (a)>(b)?(a):(b) int ans, tmp, cnt[10]; char str[10]; int main() { scanf("%s", str); for (int i = 0; i < strlen(str); i++) cnt[str[i] - '0']++; for (int i = 0; i <= 9; i++) if (i != 6 && i != 9) ans = max(ans, cnt[i]); ans = max(ans, (cnt[6] + cnt[9] + 1)...
-
[BOJ] 10159 : 저울
10159 : 저울 풀이 a와 b의 대소관계를 알 수 있다는 것은 a에서 b까지 알고 있는 관계를 건너건너 도착할 수 있다는 것이고 n 제한이 100으로 엄청 작으므로 모든 경로를 구해놓자. 그리고 도달할 수 없는 노드의 개수를 세어주자. 코드 #include <stdio.h> int n, m, a[101][101]; int main() { scanf("%d %d", &n, &m); for (int i = 0, x, y; i < m; i++) scanf("%d %d", &x, &y), a[x][y] = 1; for (int k = 1; k <=...
-
[BOJ] 10158 : 개미
10158 : 개미 풀이 개미가 움직이는 w*h 크기의 격자가 사방에 이어붙여져 있다고 생각해보자. w - abs(w - (x + t) % (2 * w)), h - abs(h - (y + t) % (2 * h)) 나머지 연산을 이용하면 간단하게 풀 수 있다. 코드 #include <bits/stdc++.h> int w, h, x, y, t; int main() { scanf("%d %d %d %d %d", &w, &h, &x, &y, &t); printf("%d %d", w - abs(w - (x + t) % (2...
-
[BOJ] 10157 : 자리배정
10157 : 자리배정 풀이 달팽이 짜듯이 하면 된다 코드 #include <stdio.h> const int dx[] = { 1,0,-1,0 }; const int dy[] = { 0,1,0,-1 }; int n, m, c, a[1002][1002]; int main() { scanf("%d %d %d", &n, &m, &c); for (int i = 0; i <= 1001; i++) a[i][0] = a[0][i] = a[m + 1][i] = a[i][n + 1] = 1; int x = 0, y = 1, d = 0; for (int i =...
-
[BOJ] 10156 : 과자
10156 : 과자 풀이 꺄르륵 코드 main(a,b,c){scanf("%d%d%d",&a,&b,&c);printf("%d",a*b-c>0?a*b-c: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),...
-
[BOJ] 6191 : Cows on Skates
6191 : Cows on Skates 풀이 (1,1)~(r,c)까지의 경로를 찾아주자! 왜 이게 usaco gold 문제인지는 모르겠다 ㅋㅋㅋ 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; struct ABC { int x, y; }; int n, m; char a[123][123]; ABC chk[123][123]; queue<ABC> que; void f(int x, int y) { if (x != 1 || y != 1) f(chk[x][y].x, chk[x][y].y); printf("%d %d\n", x, y); }...
-
[BOJ] 2786 : 상근이의 레스토랑
2786 : 상근이의 레스토랑 풀이 (첫 주문) 가격과 (일반 주문) 가격이 나누어져있다. 일반 가격으로 정렬한 뒤 1~i번째 가격의 합을 구해놓고 생각하자. 그럼 두 가지의 케이스로 나눌 수 있다. 1~i번째 메뉴들 중 (첫 주문)과 (일반 주문) 가격의 차이가 가장 큰 것을 고르는 경우 i~n번째 메뉴들 중 (첫 주문)의 가격이 가장 작은 것을 고르는 경우 이제 어찌저찌여차저차 잘 짜면 된다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; typedef pair<int, int>...
-
[BOJ] 2785 : 체인
2785 : 체인 풀이 데스크립션이 이상해서 한참 고민했다 (…) 고리로 이루어진 체인들이 여럿 주어진다. 고리를 최소한으로 사용해서 모든 체인들을 일렬로 연결하고 싶다. 한 고리에는 최대 두 개의 다른 고리(체인)만 연결할 수 있다. 그리디하게 생각해보자! 체인의 수가 작아지면 필요한 고리의 수도 작아진다. 그리고 체인을 모두 고리로 분해하면 체인의 개수가 하나 줄어든다.! 길이가 가장 짧은 체인의 고리부터 사용하면 된다! 같은 양의 고리를 사용하더라도 길이가 짧은 것부터 사용해야 체인의 수를 조금이나마 더 줄일 수 있다. 코드 #include <stdio.h>...
-
[BOJ] 2784 : 가로 세로 퍼즐
2784 : 가로 세로 퍼즐 풀이 n 제한이 굉장히 작으므로 naive하게 그냥 다 돌려보면 된다! 코드 #include <iostream> #include <string> #include <algorithm> using namespace std; string pzl[3], wrd[6]; void wookje() { bool chk[6] = { 0 }; int cnt = 0; for (int k = 0; k < 3; k++) { for (int i = 0; i < 6; i++) { if (!chk[i] && pzl[k] == wrd[i]) { chk[i] = 1, cnt++; break; } }...
-
[BOJ] 2783 : 삼각 김밥
2783 : 삼각 김밥 풀이 그냥 짜면 된다! 코드 #include <stdio.h> double a, b, n, f; int main() { scanf("%lf %lf %lf", &a, &b, &n); f = a / b; while (n--) { scanf("%lf %lf", &a, &b); f = f < a / b ? f : a / b; } printf("%lf", f * 1000); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘,...
-
[BOJ] 2459 : 철사 자르기
2459 : 철사 자르기 풀이 문제를 끝까지 안 읽어서 직선의 위치를 직접 정해야 하는 줄 알았는데 알고보니 직선의 위치를 문제에서 주는 거였다. i번째 점과 i+1번째 점의 좌표를 이용해서 어찌저찌 잘 짜면 된다. 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; int n, k, l; pair<int, int> p[100002]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < k; i++) scanf("%d %d", &p[i].fst, &p[i].snd); p[k++] = { 1,1...
-
[BOJ] 2458 : 키 순서
2458 : 키 순서 풀이 모든 노드에서 dfs를 정방향으로 한 번, 역방향으로 한 번 돌려주자! 정방향은 나보다 큰 친구들, 역방향은 나보다 큰 친구들의 개수(?)이다. 이 둘을 합한 값이 나를 제외한 n-1명과 같은지 알아보자! 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, vst[2][501]; vector<int> gph[2][501]; int dfs(int now) { int ret = 1; vst[t][now] = 1; for (int nxt : gph[t][now]) if (!vst[t][nxt]) ret += dfs(nxt); return ret; } int main() { int u,...
-
[BOJ] 2457 : 공주님의 정원
2457 : 공주님의 정원 풀이 회의실 배정 문제에 날짜가 추가된 버전이다. 정렬해서 그리디를 돌리면 된다. 날짜를 처리하기가 조금 까다롭다. 하지만 까다로운 건 싫다. 그렇다면 month에 100을 곱해보자. 기적이 일어난다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n; pair<int, int> f[100001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c,...
-
[BOJ] 2456 : 나는 학급회장이다
2456 : 나는 학급회장이다 풀이 완전 쌩노가다 문제! 점수 합이 같은 경우에는 높은 점수의 개수(?)를 비교해야 한다. 점수의 개수를 카운팅하지 말고, 점수를 제곱해서 더해주자! 점수의 개수에 따라 제곱합 값이 달라지기 때문에 점수의 개수가 다르다면 unique함이 보장된다. 잔재주를 조금 부리면 코드 길이를 엄청 줄일 수 있다. 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, f; pair<int, int> p[3]; int main() { scanf("%d", &n); for (int i = 0;...
-
[BOJ] 2455 : 지능형 기차
2455 : 지능형 기차 풀이 기차 뿌뿌 코드 #include <stdio.h> int s, m; int main() { for (int i = 0; i < 4; i++) { int a, b; scanf("%d %d", &a, &b); s = s - a + b; m = m > s ? m : s; } printf("%d", m); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge
-
[BOJ] 2565 : 전깃줄
2565 : 전깃줄 풀이 LIS를 구해주자! 주어진 두 축을 주어진 선으로 연결했을 때 겹치는 선이 없어야 한다! 한 축 x를 기준으로 잡아 pair를 정렬해주자. 이제 정렬한 축 x를 기준으로 한바퀴 쭉 돌면서 순서대로 마주치는 y축에 대해서 LIS를 수행해주자! 코드 #include <stdio.h> #include <algorithm> #define fst first #define snd second using namespace std; int n, len, lis[100]; pair<int, int> a[100]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d %d",...
-
[BOJ] 1735 : 분수 합
1735 : 분수 합 풀이 중학교의 추억을 되새겨보자! 룰루랄라~ 코드 #include <stdio.h> int a, b, c, d; int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } int main() { scanf("%d %d %d %d", &a, &b, &c, &d); a = a*d + b*c, c = b*d, b = gcd(a, c); printf("%d %d", a/b, c/b); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA,...
-
[BOJ] 9251 : LCS
9251 : LCS 풀이 dp[i][j] = a[1~i]와 b[1~j]의 LCS 값 dp[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j])) 코드 #include <stdio.h> #include <algorithm> char a[1111], b[1111]; int i, j, d[1111][1111]; int main() { scanf("%s\n%s", a + 1, b + 1); for (i = 1; a[i]; i++) for (j = 1; b[j]; j++) d[i][j] = std::max({ d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]) }); printf("%d", d[i-1][j-1]); return 0; } 아무말 백준, 백준 온라인 저지, BOJ,...
-
[BOJ] 1965 : 상자넣기
1965 : 상자넣기 풀이 lower bound를 써주자! 더 큰 상자가 최소 어디에 들어갈 수 있는지 lower bound로 찾으면 된다! O(n^2) dp대신에 lower bound를 써주면 O(nlogn)에 풀 수 있따! 코드 #include <stdio.h> #include <algorithm> using namespace std; int n, len, a[1001]; int main() { scanf("%d", &n); while (n--) { int tmp; scanf("%d", &tmp); auto it = lower_bound(a, a + len, tmp); if (*it == 0) len++; *it = tmp; } printf("%d", len); return 0; } 아무말...
-
[BOJ] 11055 : 가장 큰 증가 부분 수열
11055 : 가장 큰 증가 부분 수열 풀이 d[i] = i번째 수까지의 부분 수열 중 최댓값으로 놓자! d[i] = d[j] + a[i] lis에서 dp 배열에 길이를 넣는 것 대신 최댓값을 넣어주면 된다. 코드 #include <stdio.h> int n, ans, a[1001], d[1001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); d[i] = a[i]; for (int j = 0; j <= i; j++) { if (a[j] < a[i] &&...
-
[BOJ] 1699 : 제곱수의 합
1699 : 제곱수의 합 풀이 knapsack 풀듯이 똑같이 풀면 된다! 배낭에 무게가 i*i이고 가치가 1인 돌덩이들을 넣는다고 생각하자! dp[j] = min(dp[j-i*i] + 1, dp[j]) 코드 #include <stdio.h> int n, d[100001]; int min(int a, int b) { return a < b ? a : b; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) d[i] = 1e9; for (int i = 1; i*i <= n; i++) for (int j =...
-
[BOJ] 1309 : 동물원
1309 : 동물원 풀이 d1[i] = 2*i인 우리에서 i번째 칸에 사자를 0마리 놓는 경우의 수 d2[i] = 2*i인 우리에서 i번째 칸의 한 쪽에만 사자를 1마리 놓는 경우의 수 d1[i] = d1[i-1] + d2[i-1] * 2 d2[i] = d1[i-1] + d2[i-1] 위의 식을 그대로 써도 좋지만, 1차원으로 더 압축해보자! 위에서 정의한 d1과 d2를 잘 기억하자. d1[i] = d1[i-1] + d2[i-1] * 2 d1[i] = (d1[i-2] + d2[i-2] * 2) + (d1[i-2] + d2[i-2]) * 2 d1[i]...
-
[BOJ] 2133 : 타일 채우기
2133 : 타일 채우기 풀이 타일은 n이 짝수인 경우에만 완벽히 채울 수 있다. 2*1 타일을 맨위와 맨아래에 일렬로 배치하는 경우에 유의하자. dp[i] = dp[i-2] * 3 + dp[i-j] * 2 (4 <= i, 4 <= j <= i) 코드 #include <stdio.h> int main() { int n, d[31] = { 1,0,3 }; scanf("%d", &n); for (int i = 4; i <= n; i += 2) { d[i] = d[i - 2] * 3; for (int j...
-
[BOJ] 1316 : 그룹 단어 체커
1316 : 그룹 단어 체커 풀이 i번째 문자와 i-1번째 문자가 같다면 둘은 연속된 문자이므로 같은 그룹에 속한다. 단어가 그룹에 속해있지 않는 경우는 이미 앞에서 동일한 문자가 나왔고, i번째 문자와 i-1번째 문자가 다른 경우이다. 체킹 배열을 만들어서 체크해주자! 코드 #include <iostream> #include <string> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tc, ans = 0; string str; cin >> tc; while (tc--) { bool chk[26] = { 0 }, flg = 0; cin >> str;...
-
[BOJ] 11509 : 풍선 맞추기
11509 : 풍선 맞추기 풀이 높이 a의 풍선을 볼 때, a+1 높이에서 날아오는 화살이 있는지 검사해주자! 코드 #include <iostream> using namespace std; int n, a, i, ans, cnt[1000001]; int main() { std::ios_base::sync_with_stdio(false); cin >> n; for (i = 0; i < n; i++) { cin >> a; if (!cnt[a+1]) cnt[a]++, ans++; else cnt[a+1]--, cnt[a]++; } cout << ans; return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge
-
[BOJ] 2501 : 약수 구하기
2501 : 약수 구하기 풀이 ㅎㅎ 코드 #include <stdio.h> int main() { int n, k, cnt=0; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { if (!(n%i)) cnt++; if (cnt == k) { printf("%d", i); return 0; } } puts("0"); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 11508 : 2+1 세일
11508 : 2+1 세일 풀이 ㅎㅎ 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, sum = 0, c[100001]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &c[i]), sum += c[i]; std::sort(c, c + n); for (i = n - 3; i >= 0; i -= 3) sum -= c[i]; for (i = 0; i < i % 3; i++) sum -= c[i]; printf("%d", sum); return 0; } 아무말 백준,...
-
[BOJ] 11507 : 카드셋트
11507 : 카드셋트 풀이 ㅎㅎ 코드 #include <stdio.h> int a, b, cnt[4]; bool chk[14][4]; int main() { for (char c; ~scanf("%c%1d%1d", &c, &a, &b);) { a = a * 10 + b; switch (c) { case 'P': c = 0; break; case 'K': c = 1; break; case 'H': c = 2; break; case 'T': c = 3; } if (chk[a][c]) { puts("GRESKA"); return 0; } chk[a][c] = 1, cnt[c]++; } for (int i =...
-
[BOJ] 14438 : 수열과 쿼리 17
14438 : 수열과 쿼리 17 풀이 sqrt decomposition을 이용해서 풀었다. 물론 segment tree를 이용하면 훨씬 더 빠르다. 코드 #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; int n, m, sqr, a[100001], bkt[100001]; void upd(int i, int v) { a[i] = v, bkt[i / sqr] = 1e9 + 1e8; int tmp = i / sqr; for (int j = tmp * sqr; j < (tmp + 1) * sqr; j++) bkt[tmp] = min(bkt[tmp], a[j]); }...
-
[BOJ] 2591 : 숫자카드
2591 : 숫자카드 풀이 n-1번째 숫자와 n번째 숫자로 만든 값이 10~34면 dp[n-2]를 플러스 n번째 숫자가 0보다 크면(단독으로 숫자를 구성할 수 있으면) dp[n-1]을 플러스 코드 #include <stdio.h> int i, a[44], dp[44]; int main() { dp[1] = 1; for (i = 2; ~scanf("%1d", &a[i]); i++) { if (a[i]) dp[i] += dp[i - 1]; if (a[i] + a[i - 1] * 10 > 9 && a[i] + a[i - 1] * 10 < 35) dp[i] += dp[i -...
-
[BOJ] 14572 : 스터디 그룹
14572 : 스터디 그룹 풀이 학생들이 아는 모든 알고리즘의 수는 bit OR 연산과 같다. 이는 항상 같거나 증가한다. 모든 학생들이 아는 알고리즘의 수는 bit AND 연산과 같다. 이는 항상 같거나 감소한다. 따라서 누구는 빼고 누구는 넣고 할 것 없이 능력치 조건을 만족하는 범위 내의 모든 학생들을 선택해도 된다. 학생들을 능력치를 기준으로 정렬한 다음, 투 포인터를 사용하면 쉽게 답을 찾을 수 있다. 코드 #include <stdio.h> #include <algorithm> using namespace std; const int n_ = 1e5 +...
-
[BOJ] 14571 : 모래시계
14571 : 모래시계 풀이 임의의 두 인접한 사이클은 하나 또는 두개의 노드를 공유할 수 있으므로 두 경우의 수를 모두 구해서 겹치는 경우를 제거하자 컴비네이션으로 구하면 쉽게 구할 수 있다. 코드 #include <stdio.h> #include <vector> using namespace std; typedef long long ll; const int n_ = 200; int n, m, one[n_], two[n_][n_]; bool gph[n_][n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d",...
-
[BOJ] 14570 : 나무 위의 구슬
14570 : 나무 위의 구슬 풀이 문제의 조건을 그대로 가져다 써보자. 모든 노드에 대해, 왼쪽 구슬의 수가 오른쪽 구슬의 수보다 크거나 같다. n개의 구슬 중 n/2+n%2개는 왼쪽, n/2개는 오른쪽으로 떨어지게 된다. 종단 노드를 만날 때 까지 돌려보자~~ 코드 #include <stdio.h> struct hello { int l, r; } t[200001]; int main() { int n; long long k; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d %d", &t[i].l, &t[i].r); scanf("%lld", &k); int cur...
-
[BOJ] 14569 : 시간표 짜기
14569 : 시간표 짜기 풀이 모든 경우를 다 돌려보면 된다. bit를 사용하면 편하게 짤 수 있다. 코드 #include <stdio.h> typedef unsigned long long ull; ull t[1001]; int main() { int n, m, k; scanf("%d", &n); for (int i = 0; i < n; i++) { int k, a; scanf("%d", &k); for (int j = 0; j < k; j++) scanf("%d", &a), t[i] |= ((ull)1 << a); } scanf("%d", &m); for (int i = 0; i...
-
[BOJ] 14568 : 2017 연세대학교 프로그래밍 경시대회
14568 : 2017 연세대학교 프로그래밍 경시대회 풀이 택희가 받는 사탕의 개수를 i로 두고 구하면 된다. n개 사탕 중에서 택희 사탕 i개와 영훈이랑 남규의 사탕 차이 2개를 뺀 사탕 갯수 n-i-2에서 (영훈 <= 남규)를 만족하는 조합의 수는 (n-i-2)/2와 같다. ex1) 5를 나누는 경우: (1,4), (2,3) ex2) 6를 나누는 경우: (1,5), (2,4), (3,3) 코드 #include <stdio.h> int n, sum; int main() { scanf("%d", &n); for (int i = 2; i <= n - 2; i += 2)...
-
[BOJ] 13910 : 개업
13910 : 개업 풀이 웍을 최대 2개까지 사용할 수 있으므로 가능한 조합을 모두 구해둔다 그리고 점화식 세워서 풀면 된다. dp[n] = min(dp[n-i]+1,dp[n]) 코드 #include <stdio.h> int main() { int n, m, i, j, a[101], dp[10001]; bool chk[22222] = { 0 }; scanf("%d %d", &n, &m); for (i = 0; i <= n; i++) dp[i] = 1e9; chk[0] = 1; dp[0] = 0; for (i = 0; i < m; i++) scanf("%d", &a[i]); for (i =...
-
[BOJ] 2583 : 영역 구하기
2583 : 영역 구하기 풀이 직사각형 영역에 체크를 해놓고 모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다. 입력이 좀 짜증난다 (…) 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; int n, m, k, cnt, a[111][111]; vector<int> v; int dfs(int x, int y) { int ret = 1; a[x][y] = 1; for (int i = 0; i < 4; i++)...
-
[BOJ] 1107 : 리모컨
1107 : 리모컨 풀이 그냥 다 돌려보자! 코드 #include <stdio.h> int n, m, i, k, ans, res; bool chk[10]; int hi(int a) { int cnt = 0; while (a) { if (chk[a % 10]) return -1; a /= 10; cnt++; } return cnt; } int main() { scanf("%d %d", &n, &m); for (i = 0; i < m; i++) scanf("%d", &k), chk[k] = true; ans = n - 100; if (ans < 0) ans =...
-
[BOJ] 2010 : 플러그
2010 : 플러그 풀이 새로운 멀티탭의 플러그 수에서 하나를 뺀 값을 더해주면 된다. 코드 #include <stdio.h> int main() { int n, i, k, sum = 1; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&k); sum += k-1; } printf("%d",sum); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이
-
[BOJ] 1414 : 불우이웃돕기
1414 : 불우이웃돕기 풀이 미니멈 스패닝 트리를 쓰자. 크루스칼을 쓰자. 전체 랜선의 합에서 최소로 잇는 랜선의 합을 빼주자. 자잘한 처리가 조금 귀찮은 문제다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct edg { int x, y, w; edg(int x, int y, int w) :x(x), y(y), w(w) {} bool operator <(edg A)const { return w < A.w; } }; int n, pnt[101]; vector<edg> gph; int find(int u) { if (u == pnt[u]) return...
-
[BOJ] 1411 : 비슷한 단어
1411 : 비슷한 단어 풀이 뭔가 번역이 좀 애매한 것 같은데 a->b면 b->a도 당연히 성립할 줄 알았더니 a->b만 성립하면 되는 문제였다 (…) 단순 구현 문제이다. 코드 #include <iostream> #include <string> using namespace std; int n, i, j, k, ans; string str[101]; int main() { scanf("%d", &n); for (i = 0; i < n; i++) cin >> str[i]; for (i = 0; i < n - 1; i++) for (j = i + 1; j <...
-
[BOJ] 9466 : 텀 프로젝트
9466 : 텀 프로젝트E 풀이 위상정렬을 하자! 코드 #include <stdio.h> #include <memory.h> const int n_ = 100000 + 1; int ans, a[n_], idg[n_]; bool chk[n_]; void dfs(int n) { chk[n] = true; ++ans, --idg[a[n]]; if (!chk[a[n]] && !idg[a[n]]) dfs(a[n]); } int main() { int t, n, i, j; scanf("%d", &t); for (i = 1; i <= t; ++i) { ans = 0; scanf("%d", &n); memset(chk, 0, sizeof(chk)); memset(idg, 0, sizeof(idg)); for (j = 1; j...
-
[BOJ] 13023 : ABCDE
13023 : ABCDE 풀이 A-B-C-D-E 관계의 5명이 있는지 구하는 문제였다. dfs를 돌려주자. 코드 #include <stdio.h> #include <memory.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 2000 + 1; bool ans, chk[n_]; int n, m; vector<int> v[n_]; void dfs(int now, int cnt) { if (cnt == 5) { ans = true; return; } chk[now] = true; for (int next : v[now]) { if (!chk[next]) dfs(next, cnt + 1); if (ans) return; } chk[now]...
-
[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_],...
-
[BOJ] 11438 : LCA2
11438 : LCA2 풀이 이번엔 naive가 아닌 풀이! 이전의 naive한 풀이에서, 우리는 최악의 경우에 n번의 노드를 하나씩하나씩 올라가야했다. 하지만 이를 log(n)으로 줄일 수 있다! pnt[i][j] = i번 노드의 2^j번째 조상으로 두고 풀면 된다. 트리의 깊이를 구할 때 2^j번째 조상을 구해두자. tmp = anc[i][j-1]일 때, anc[i][j]는 anc[tmp][j-1]과 같다. 즉, i의 2^j번째 조상은 2^(j-1)번째 조상의 2^(j-1)번째 조상과 같다는 의미이다. i의 2^3=8번째 조상은 2^2=4번째 조상의 2^2=4번째 조상과 같다. naive한 코드에서 2^j를 도는 동작만 추가해주면 어렵지 않게(?) 훨씬 빠르게(!)...
-
[BOJ] 11437 : LCA
11437 : LCA 풀이 naive한 풀이! dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤, u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에 두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 5e4 + 3; int n, m; int dph[n_], pnt[n_]; vector<int> gph[n_]; inline void dfs(int now, int cnt) { dph[now] = cnt++; for (auto...
-
[BOJ] 13306 : 트리
13306 : 트리 풀이 엣지를 제거하면서 union find를 하려면 TLE가 난다. 문제를 거꾸로 생각하자. 원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다. 그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?! 간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다. 발상의 전환이 조금 어려운 문제인 것 같다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 3; int n, q; int gph[n_], pnt[n_], q1[n_ * 2],...
-
[BOJ] 11052 : 붕어빵 판매하기
11052 : 붕어빵 판매하기 풀이 dp[i] = 붕어빵 i개를 팔았을 때의 최댓값 dp[i] = i-j번째 최댓값 + j개 세트의 가격 코드 #include <stdio.h> int n, i, j, a[1001], dp[1001]; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) if (dp[i] < dp[i - j] + a[j]) dp[i] = dp[i - j] + a[j];...
-
[BOJ] 1110 : 더하기 사이클
1110 : 더하기 사이클 풀이 do while 처음 써봤다 ㅋㅋ 코드 #include <stdio.h> int main() { int n, m, c = 0; scanf("%d", &n); m = n; do { c++, m = (m % 10) * 10 + (m / 10 + m % 10) % 10; } while (n != m); printf("%d", c); return 0; } 아무말 백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조,...
-
[BOJ] 2262 : 토너먼트 만들기
2262 : 토너먼트 만들기 풀이 큰 수가 많이 자주 올라갈 수록 합은 크게 나온다. 그렇다면 가장 큰 수 부터 묶어주면 된다! 코드 #include <stdio.h> int max(int a, int b) { return a > b ? a : b; } int n, i, j, a[257], ans; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i = n; i > 1; i--) { for (j = 1; j <=...
-
[codeforces] #403 div1 A (div2 C)
#403 div1 A. Andryusha and Colored Balloons 풀이 이전 노드의 색, 이번 노드의 색에 대한 정보를 가지고 dfs를 돌리면 해결할 수 있다. 추가로, (가장 큰 차수)+1만 가지고 최소로 색칠할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 10; int n, ans, col[n_]; vector<int> gph[n_]; void dfs(int prv, int cur) { int i = 1; for (auto nxt : gph[cur]) { if (col[nxt]) continue; while (col[prv] == i || col[cur]...
-
[codeforces] #403 div2 B
#403 div2 B. The Meeting Place Cannot Be Changed 풀이 코포 문제는 처음 풀이한다! (두근두근) 이분 탐색을 돌리면 쉽게 해결할 수 있다. 만나는 시간을 mid로 두면, n*log(최대차이)이므로 제한시간에 맞게 돌릴 수 있다. 각각의 좌표 x[i]를 돌면서 mid에 갈 수 있는 max_left, min_right를 구한다. max_left <= min_right면 mid에 만날 수 있다. 왜 그런지는 그림판에 대충 선 몇 개 그려보면 직관적으로 이해 될 것이다. (아마?) AC 받긴 했는데 저렇게 짜도 실수 오차 안 나는지는 모르겠다 (…) 코드...
-
[BOJ] 1080 : 행렬
1080 : 행렬 풀이 그냥 그리디하게 (i,j)가 다르면 바꿔주면 된다! 코드 #include <stdio.h> int main() { int i, j, x, y, ans = 0, n, m; char a[51][51], b[51][51]; scanf("%d %d", &n, &m); for (i = 0; i < n; i++) scanf("%s", a[i]); for (i = 0; i < n; i++) scanf("%s", b[i]); for (i = 0; i < n - 2; i++) { for (j = 0; j < m - 2; j++) {...
-
[BOJ] 1922 : 네트워크 연결
1922 : 네트워크 연결 풀이 계절이 지나가는 하늘에는 가을로 가득 차 있습니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e3 + 1; const int m_ = 1e5 + 1; struct node { int u, v, w; } edg[m_]; int p[n_]; inline int find(int u) { if (u == p[u]) return u; return p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v);...
-
[BOJ] 1937 : 욕심쟁이 판다
1937 : 욕심쟁이 판다 풀이 dfs를 돌리자! 코드 #include <stdio.h> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; const int n_ = 500 + 5; int n, a[n_][n_], dp[n_][n_]; inline int max(int a, int b) { return a > b ? a : b; } int dfs(int x, int y) { if (dp[x][y]) return dp[x][y]; dp[x][y] = 1; for (int i = 0; i < 4; i++) { int...
-
[BOJ] 2839 : 설탕배달
2839 : 설탕배달 풀이 dp[i] = min(dp[i-3], dp[i-5]) + 1로 두고 풀면 된다. n이 5천개니까 max를 대충 1600?쯤 잡으면 3으로 꽉채워도 최대 해보다 작고 max를 5천개 더해도 int 안쪽이니까 max를 2222로 잡았다. 코드 #include <stdio.h> int min(int a, int b) { return a < b ? a : b; } int main() { int n, i, a[5001]; scanf("%d", &n); for (i = 0; i <= n; i++) a[i] = 2222; a[3] = a[5] = 1;...
-
[BOJ] 1261 : 알고스팟
1261 : 알고스팟 풀이 다익스트라를 변형해보자 dp랑 적당히 섞어보자 코드 #include <cstdio> #include <queue> using namespace std; const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; const int n_ = 100 + 5; struct edg { int x, y, w; bool operator <(edg A)const { return w > A.w; } }; int main() { int n, m, chk[n_][n_] = {}; char a[n_][n_]; priority_queue<edg> pq; scanf("%d %d\n", &m, &n); for (int i =...
-
[BOJ] 1197 : 최소 스패닝 트리
1197 : 최소 스패닝 트리 풀이 크루스칼을 하자. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 1; const int m_ = 1e5 + 1; struct node { int u, v, c; bool operator <(node A)const { return c < A.c; } } edg[m_]; int n, m; int mom[n_]; int find(int u) { if (u == mom[u]) return u; return mom[u] = find(mom[u]); } void merge(int u, int...
-
[BOJ] 1026 : 보물
1026 : 보물 풀이 하나는 오름차순, 하나는 내림차순으로 정렬하고 곱해주면 된다! 코드 #include <stdio.h> #include <algorithm> int main() { int n, i, a[101], b[101], c = 0; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &a[i]); for (i = 0; i < n; i++) scanf("%d", &b[i]); std::sort(a, a + n); std::sort(b, b + n, [](const int &i, const int &j){return i > j;}); for (i = 0; i < n; i++) c...
-
[BOJ] 1012 : 유기농 배추
1012 : 유기농 배추 풀이 DFS를 돌리자. 코드 #include <stdio.h> #include <memory.h> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int tc, n, m, k, i, j, x, y, ans; bool farm[52][52]; void dfs(int x, int y) { farm[x][y] = 0; for (int i = 0; i < 4; i++) if (farm[x + dx[i]][y + dy[i]]) dfs(x + dx[i], y + dy[i]); } int main() { scanf("%d", &tc); while...
-
[BOJ] 2623 : 음악프로그램
2623 : 음악프로그램 풀이 위상정렬을 하면 된다! 코드 #include <iostream> #include <vector> using namespace std; const int n_ = 1000 + 3; int n, m, idg[n_]; vector<int> ans; vector<int> edg[n_]; void dfs(int now) { idg[now] = -1; ans.push_back(now); for (auto nxt : edg[now]) if (!(--idg[nxt])) dfs(nxt); } int main() { int i, j, a, b, c; cin >> n >> m; while (m--) { cin >> a >> b; while (--a) { cin >> c;...
-
[BOJ] 2511 : 카드놀이
2511 : 카드놀이 풀이 구현을 하자. 코드 #include <bits/stdc++.h> using namespace std; int a[10], b[10], i, A, B, p; int main() { for (i = 0; i < 10; i++) scanf("%d", &a[i]); for (i = 0; i < 10; i++) scanf("%d", &b[i]); for (i = 0; i < 10; i++) { if (a[i] > b[i]) A += 3, p = 0; else if (a[i] < b[i]) B += 3, p = 1; else A++, B++;...
-
[BOJ] 1509 : 팰린드롬 분할
1509 : 팰린드롬 분할 풀이 나중에 써야징 코드 #include <stdio.h> #include <string.h> const int n_ = 2500 + 5; int len, dp[n_][n_], res[n_]; char data[n_]; int main() { scanf("%s", data); len = strlen(data); for (int i = 1; i <= len; i++) dp[i][i] = 1; for (int i = 1; i <= len - 1; i++) if (data[i - 1] == data[i]) dp[i][i + 1] = 1; for (int i = 2; i <= len...
-
[BOJ] 10828 : 스택
10828 : 스택 풀이 스택을 쓰자. 코드 #include <bits/stdc++.h> using namespace std; int n, a; stack<int> sta; string str; int main() { for (scanf("%d", &n); n; n--) { cin >> str; if (str == "push") { scanf("%d", &a); sta.push(a); } else if (str == "pop") { if (sta.empty()) printf("-1\n"); else printf("%d\n", sta.top()), sta.pop(); } else if (str == "size") { printf("%d\n", sta.size()); } else if (str == "empty") { printf("%d\n", sta.empty()); } else { if...
-
[BOJ] 13308 : 주유소
13308 : 주유소 풀이 2016 koi 전국대회 2번 문제이다. 뭔가 코드가 dp인 것 같기도 하고 아닌 것 같기도 한데 어쨌든 다익스트라+dp 그런 느낌으로 풀었다. 음 생각해보니 dp가 맞네 dp[i][j] = 노드i에서 기름값j로 놓고 풀면 된다! 여기서 트릭(?)을 한 번 써보자. priority_queue에서 dst가 가장 작은 노드부터 꺼내기 때문에 dp[i][j] (== vst[i][j])에 방문했었다면 이미 지금보다 작은 값으로 방문했었음이 보장된다. 그래서 bfs 돌릴 때랑 똑같이 풀면 된다. visted면 방문하지 않아도 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef...
-
[BOJ] 11866 : 조세퍼스 문제 0
11866 : 조세퍼스 문제 0 풀이 단순 구현 코드 #include <bits/stdc++.h> using namespace std; int n, m, pos; vector<int> a; int main() { cin >> n >> m; for (int i = 0; i < n; i++) a.push_back(i + 1); printf("<"); while (1) { pos = (pos + m - 1) % a.size(); if (a.size() > 1) { printf("%d, ", a[pos]); } else { printf("%d>", a[pos]); break; } a.erase(a.begin() + pos); } return 0; }...
-
[BOJ] 4963 : 섬의 개수
4963 : 섬의 개수 풀이 dfs를 돌리자 코드 #include <stdio.h> const int dx[] = { 0,0,1,-1,1,1,-1,-1 }; const int dy[] = { -1,1,0,0,1,-1,-1,1 }; int n, m; int a[51][51]; void dfs(int x, int y) { a[x][y] = 0; for (int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m)...
-
[BOJ] 10799 : 쇠막대기
10799 : 쇠막대기 풀이 괄호가 나오는 문제는 대부분 stack을 이용하면 풀린다! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; int cnt, ans; string str; int cmp(char a, char b) { a -= '(', b -= '('; if (a == 0 && b == 0) return 1; if (a == 0 && b == 1) return 2; if (a == 1 && b == 0) return 3; if (a == 1 && b == 1) return 4;...
-
[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...
-
[BOJ] 13302 : 리조트
13302 : 리조트 풀이 다이나믹 프로그래밍! dp[i][j] = i번째 날에 쿠폰 개수가 j인 경우의 수! 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 100 + 10; const int price[] = { 0,10000,25000,37000 }; const int INF = 987654321; int n, m; int dp[n_][n_ * 2]; bool chk[n_]; void upd(int i, int j, int v) { if (dp[i][j] > v || dp[i][j] == INF) dp[i][j] = v; } int main() { scanf("%d %d",...
-
[BOJ] 1786 : 찾기
1786 : 찾기 풀이 KMP 룰루랄라 코드 #include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N_ = 1e6 + 5; int fail[N_], t_len, p_len; char T[N_], P[N_]; int main() { gets_s(T); t_len = strlen(T); gets_s(P); p_len = strlen(P); for (int i = 1, j = 0; i < p_len; ++i) { while (j && P[i] != P[j]) j = fail[j - 1]; if (P[i] == P[j]) fail[i] = ++j; } vector<int> ans;...
-
[BOJ] 1701 : Cubeditor
1701 : Cubeditor 풀이 Naive한 풀이 룰루랄라 코드 #include <bits/stdc++.h> using namespace std; int ans, cnt; char str[5001]; vector<string> suf; int main() { scanf("%s", str); for (int i = 0; i < strlen(str); ++i) { suf.push_back(str + i); } sort(suf.begin(), suf.end()); for (int i = 0; i < suf.size() - 1; ++i) { while (suf[i][cnt] == suf[i + 1][cnt]) ++cnt; ans = max(ans, cnt); cnt = 0; } printf("%d", ans); return 0; } 아무말 백준,...
-
[BOJ] 7976 : 수열
7976 : 수열 풀이 좋은 풀이는 여기에 있다! 핵심은 이거: dp[i][j] = i번까지의합 % 2가 j인 최소 변환 횟수 코드 #include <stdio.h> #include <algorithm> using namespace std; int N, K; int cnt[1000001][2], dp[1000001][2]; int main() { scanf("%d %d", &N, &K); for (int i = 0; i < N; ++i) { int a; scanf("%d", &a); ++cnt[i % K + 1][a & 1]; } dp[0][1] = 1e9; for (int i = 1; i <= K; ++i) {...
-
[BOJ] 1019 : 책 페이지
1019 : 책 페이지 풀이 나중에 써야지~ 코드 #include <stdio.h> int N, prev; int cnt[10]; int main() { scanf("%d", &N); for (int i = 1; N; i *= 10) { int now = N % 10; N /= 10; for (int j = 0; j < now; ++j) cnt[j] += (N + 1) * i; cnt[now] += N * i + prev + 1; for (int j = now + 1; j < 10; ++j)...
-
[BOJ] 12101 : 1, 2, 3 더하기 2
12101 : 1, 2, 3 더하기 2 풀이 지금 생각해보니 스택으로 짜도 될 것 같다. 코드 #include <stdio.h> #include <vector> using namespace std; int N, K; int res; vector<int> ans; bool go(int sum, int cnt) { if (sum == N) ++res; if (res == K) return true; for (int i = 1; i <= 3; ++i) { if (sum + i <= N) { if (go(sum + i, cnt + 1)) { ans.push_back(i); return true;...
-
[BOJ] 14442 : 벽 부수고 이동하기 2
14442 : 벽 부수고 이동하기 2 풀이 dp[x][y][부순 벽의 수 k]로 두고 풀자. BFS를 돌리면 된다. 하지만 중요한 건 문제 풀이가 아니고(!) memset이 byte 단위로 초기화하기 때문에 memset(dp, 1, sizeof(dp)) 하면 dp의 각 방이 0x01010101 이렇게 채워진다는 걸 배웠다. 그래서 987654321이나 1e9처럼 int_max 절반으로 초기화하고 싶으면 0x3f로 초기화하면 된다. 음… 어셈 공부하다 말았는데 계속 해야하나? ㅠㅠ 코드 #include <stdio.h> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,1,-1,0 }; const int...
-
[BOJ] 2532 : 먹이사슬
2532 : 먹이사슬 풀이 문제를 풀고 나서 다른 분들의 코드를 보다가 lower_bound를 저렇게 쓸 수 있다는 사실에 감명받았다. 양수가 음수로 변하면, 양수일 때 더 큰 수가 음수에선 더 작은 수가 되는데 양수 중에서 작은 수와 음수 중에서 가장 작은 수를 고르게 되면 넓은 범위를 찾게 된다. *lower_bound(res, res + i, now) = now;를 통해 먹이사슬인지 판단할 수 있다. 새로운 데이터가 쌓이지 못하고 덮어쓰게 되면 INF의 값이 배열의 뒤쪽에 누적되게 되고, INF의 lower_bound가 답이 된다. 코드...
-
[BOJ] 1300 : K번째 수
1300 : K번째 수 풀이 임의의 숫자 m을 골라서 K번째 숫자인지 판단해보자! 그 임의의 숫자 m은 무려 O(log K)에! 무려 이분 탐색으로 찾아보자! 그렇다면 떠오르는 질문, m 보다 작은 숫자의 개수를 어떻게 하면 빠르게 구할 수 있을까? A[i][j]에서, i행에 속한 숫자들은 i*j이므로 모두 i의 배수이다. 그러므로 min(mid/i, N)이 i번째 행에서 mid보다 작은(= 임의의 m보다 작은) 숫자들의 개수가 된다. eg. N = 1000인 경우, 첫 mid가 1000*1000/2 = 50만이 되는데, 50만/i가 N을 넘어갈 수 있으므로 min(mid/i,...
-
[BOJ] 14434 : 놀이기구1
14434 : 놀이기구1 풀이 머그컵 문제! parallel binary search를 사용하면 된다! 자세한 풀이는 여기에 있다. 헤헤 놀이기구2도 풀어봐야지 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int MAX = 2e5 + 3; int N, M, K, Q; int lim[MAX], ans[MAX]; vector<int> grow[MAX]; inline int get_sum(int u, int v, int k) { int ret1 = upper_bound(grow[u].begin(), grow[u].end(), k) - grow[u].begin(); int ret2 = upper_bound(grow[v].begin(), grow[v].end(), k) - grow[v].begin(); return ret1 + ret2; }...
-
[BOJ] 1162 : 도로포장
1162 : 도로포장 풀이 dp[노드번호i][포장갯수k]로 놓고 다익스트라를 돌리자! 원래 다익스트라에서 사용하던 dist[i]대신 dp[i][j]를 참조하면서 돌면 된다. now.dst는 지금까지 누적해 온 dst값이고, nxt.dst는 노드 사이의 거리(가중치)이다. 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int n_ = 10000 + 1; struct edg { int idx, dst, cnt; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} edg(int idx, int dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool...
-
[BOJ] 13209 : 검역소
13209 : 검역소 풀이 이분 탐색(log n)을 돌면서 그리디(n)을 돌리면 O(n log n)에 해결할 수 있다. priority_queue를 사용하기 전에 벡터를 써서 정렬하는 생각을 먼저 했지만 코딩이 괴랄해져서 포기하고 우선순위큐를 사용했다. 바이너리 서치의 mid를 비축할 백신의 수라고 두고, 주어진 검역소만으로 mid를 충족시킬 수 있는지 그리디로 풀면 된다. 싸이클이 없고 임의의 a에서 b로 가는 경로가 단 하나이기 때문에 그리디로 풀 수 있다! dfs의 리턴값은 항상 mid를 넘지 않음이 보장된다. 물론 인구수가 mid를 넘을 수는 있다. 그건 left...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...
-
[BOJ] 1992 : 쿼드트리
1992 : 쿼드트리 풀이 분할정복을 하자 네모 크기가 1일 떄 까지 내려갔다가 올라오자 코드 #include <stdio.h> int n; char a[65][65]; void gogo(int x1, int y1, int x2, int y2) { char now = a[x1][y1]; if (x1 == x2 && y1 == y2) { printf("%c", now); return; } for (int i = x1; i < x2; ++i) { for (int j = y1; j < y2; ++j) { if (now != a[i][j]) { printf("("); gogo(x1, y1,...
-
[BOJ] 1753 : 최단경로
1753 : 최단경로 풀이 다익스트라를 짜자 우선순위 큐를 쓰자 코드 #include <stdio.h> #include <algorithm> #include <queue> #include <vector> using namespace std; const int v_ = 20000 + 1; const int INF = 987654321; struct edg { int idx, dst; edg() {} edg(int idx, int dst) : idx(idx), dst(dst) {} bool operator <(edg A)const { return dst > A.dst; } }; int v, e, s, dst[v_]; vector<edg> gph[v_]; void dijkstra() { for (int i = 0;...
-
[BOJ] 10844 : 쉬운 계단 수
10844 : 쉬운 계단 수 풀이 점화식을 세우자 dp[i][j] = 총 i 자릿수이고, 가장 큰 자릿수의 숫자가 j인 경우의 수 = dp[i-1][j-1] + dp[i-1][j+1] 끗! 코드 #include <stdio.h> const int mod = 1e9; int n, i, j, dp[101][11], ans; int main() { scanf("%d", &n); for (i = 1; i <= 9; ++i) dp[1][i] = 1; for (i = 2; i <= n; ++i) for (j = 0; j <= 9; ++j) dp[i][j] = (dp[i -...
-
[BOJ] 1260 : DFS와 BFS
1260 : DFS와 BFS 풀이 bfs를 돌리자! dfs도 돌리자! 코드 #include <cstdio> #include <queue> #include <cstring> using namespace std; int n, m, v, chk[1001], gph[1001][1001]; void dfs(int now) { chk[now] = 1; printf("%d ", now); for (int i = 1; i <= n; i++) if (!chk[i] && gph[now][i]) dfs(i); } void bfs(int now) { queue<int> que; que.push(now); chk[now] = 1; while (!que.empty()) { int now = que.front(); que.pop(); printf("%d ", now); for (int i =...
-
[BOJ] 1948 : 임계경로
1948 : 임계경로 풀이 문제를 다르게 생각해보자. 마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다. 따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다! 풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야 코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다. get_max_len() 함수를 보면 일단 카운팅하기 전에...
-
[BOJ] 11758 : CCW
11758 : CCW 풀이 CCW 알고리즘의 연습문제이다. 식: S = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) S > 0 : 반시계 방향 S = 0 : 일직선 S < 0 : 시계 방향 코드 #include <stdio.h> int main() { int x1, y1, x2, y2, x3, y3, S, ans = 0; scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3); S = (x2 - x1) * (y3 -...
-
[BOJ] 머그컵 풀이
문제: https://www.acmicpc.net/contest/view/213 많은 도움 주신 스타트링크께 감사드립니다! A. 준오는 심술쟁이!! BOJ 백준 14437 준오는 심술쟁이!! 제한시간이 1초이기 때문에 단순히 3000 * 3000 * 25 dp를 돌렸다간 시간초과를 받는다. dp[문자열길이][s의 합] 일 때, 문자열 길이를 p, s 합을 q라고 하면 dp[p][q] = k가 0 ~ min(q, 25)일 때의 모든 dp[p-1][q-k]의 합 으로 점화식을 세워 해결할 수 있다. #include <iostream> #include <string> #define min(x, y) ((x)<(y)?(x):(y)) using namespace std; typedef long long ll; const int MOD =...