-
[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--;) {...
-
[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임에 주목하자. 우리는...