-
[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--;) {...
-
[KATTIS] Grid MST
Grid MST 풀이 문제가 좋아서 가져왔다. 1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은? 정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다. MST를 구성하는 상황을 생각해 보자. a-b와 b-c가 있고, b를 지나는 것이 최단인 a-c가 존재한다면, a-c를 MST에 포함시키는 것 보다 더 나은 방법(a-b, b-c)이 항상 존재한다. 격자의 크기가 최대 1000*1000임에 주목하자. 우리는...
-
[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...