-
[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--;) {...
-
[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...