-
[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] 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] 15553 : 난로
15553 : 난로 풀이 문제를 조금 다르게 생각해 보자. 일직선 상의 정수 좌표 n개가 주어졌을 때, k개 이하의 구간으로 모든 좌표를 묶어야 한다. 이 때, 구간 길이의 합을 최소로 하여라. 인접한 좌표 사이의 길이를 모두 구해놓고 생각해 보자. 상대적으로 긴 구간을 k개의 구간에 포함시키는 것은 손해이다. k개의 구간을 나눌 수 있다는 말은 구간들 중에서 k개의 길이를 답에 포함시키지 않을 수 있다는 말과 같다. 구간의 길이를 모두 구해 정렬하고 가장 작은 n-k개의 구간을 선택해 주자. 우선순위...
-
[codeforces] 1070F : Debate
1070F : Debate 풀이 11을 모두 사용해주자. 01과 10을 모두 짝 지어주고 남은 01 또는 10을 00과 섞어서 값이 가장 큰 놈들을 최대한 사용해주자. 코드 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int n, cnt, tot, sum; vector<int> v[4]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int x, y; scanf("%d %d", &x, &y); if (x == 11) cnt++, tot++, sum += y; if (x ==...
-
[codeforces] 1073D : Berland Fair
1073D : Berland Fair 풀이 안녕 내 사랑, 돌아보지마. 너 떠나도 나 울지 않을게. 부족했던 내가 더 많이 미안해. 이렇게 사랑이 끝나간다. 코드 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int n, mn = 2e9, a[200002]; ll t, ans; int main() { scanf("%d %lld", &n, &t); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (mn > a[i]) mn = a[i]; } while (mn <= t) {...
-
[BOJ] 8103 : Rooks
8103 : Rooks 풀이 요약: n*n의 체스판에 n개의 룩을 배치해야 하는데, 어떤 룩도 서로를 잡을 수 없도록 배치해야한다. 그런데 그냥 배치하는 건 아니고, 각각의 룩을 배치할 수 있는 어떤 직사각형의 영역이 n개 주어진다. 각각의 룩은 각각의 영역 내에만 배치될 수 있다. 룩은 가로/세로로만 움직일 수 있다는 사실을 조금 관찰해보면, 답을 구하는 데 있어 가로 좌표와 세로 좌표가 독립적임을 알 수 있다. 즉, 한 축(가로 또는 세로)에 대해 조건에 맞게 배치하는 일을 두 번 해주고, 나중에...
-
[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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 2785 : 체인
2785 : 체인 풀이 데스크립션이 이상해서 한참 고민했다 (…) 고리로 이루어진 체인들이 여럿 주어진다. 고리를 최소한으로 사용해서 모든 체인들을 일렬로 연결하고 싶다. 한 고리에는 최대 두 개의 다른 고리(체인)만 연결할 수 있다. 그리디하게 생각해보자! 체인의 수가 작아지면 필요한 고리의 수도 작아진다. 그리고 체인을 모두 고리로 분해하면 체인의 개수가 하나 줄어든다.! 길이가 가장 짧은 체인의 고리부터 사용하면 된다! 같은 양의 고리를 사용하더라도 길이가 짧은 것부터 사용해야 체인의 수를 조금이나마 더 줄일 수 있다. 코드 #include <stdio.h>...
-
[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] 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 <=...
-
[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] 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] 13209 : 검역소
13209 : 검역소 풀이 이분 탐색(log n)을 돌면서 그리디(n)을 돌리면 O(n log n)에 해결할 수 있다. priority_queue를 사용하기 전에 벡터를 써서 정렬하는 생각을 먼저 했지만 코딩이 괴랄해져서 포기하고 우선순위큐를 사용했다. 바이너리 서치의 mid를 비축할 백신의 수라고 두고, 주어진 검역소만으로 mid를 충족시킬 수 있는지 그리디로 풀면 된다. 싸이클이 없고 임의의 a에서 b로 가는 경로가 단 하나이기 때문에 그리디로 풀 수 있다! dfs의 리턴값은 항상 mid를 넘지 않음이 보장된다. 물론 인구수가 mid를 넘을 수는 있다. 그건 left...