-
[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>...
-
[codeforces] 1073C : Vasya and Robot
1073C : Vasya and Robot 풀이 널 향한 내 사랑은 여기까진가 봐. 그 사람 곁에서 행복하길 바라. 코드 #include <cstdio> int n, ex, ey, x[200002], y[200002]; char s[200002]; int abs(int x) { return x < 0 ? -x : x; } void f(char c, int &x, int &y) { if (c == 'U') y++; if (c == 'D') y--; if (c == 'L') x--; if (c == 'R') x++; } int main() { scanf("%d %s...
-
[BOJ] 8091 : Petrol
8091 : Petrol 풀이 KOI 주유소 문제에 자동차 연로탱크의 capacity가 추가된 버전(?) (사실 주유소 문제가 기억 안 나서 맞는지는 모름) 암튼 비슷하다. 시작점에서 끝점까지의 거리가 100만밖에 되지 않는다는 사실! 아하! 그렇다면 시작점으로부터의 거리를 인덱스로 삼는 배열을 하나 만들 수 있겠군! 오, 그럼 자동차를 한 칸씩 움직이면서 연료 탱크 최대값과 가능한 범위 내의 최소 기름값을 잘 관리하면 풀 수 있겠군!! 음… 근데 문제 분류를 어떻게 해야할지 모르겠군 코드 #include <cstdio> #include <queue> using namespace std; int...
-
[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] 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] 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...