[www.acmicpc.net/problem/18111]
#풀이
- 모든 경우를 확인해서 시간이 제일 적을 때를 출력한다.
1. 처음 땅의 높이를 입력받는다. (땅의 높이가 같은 것 끼리 묶었다.)
2. 제일 높은 땅의 높이를 max에 넣는다.
3. 모든 땅의 높이가 max일 때 부터 시작해서 0일 때 까지 모든 경우 탐색한다. (max부터 시작해 판정하지 않아도 시간이 작을 때 높이가 최대)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #pragma warning(disable: 4996) #include <stdio.h> int main() { int a, b, in, tmp, max = 0, result = 2147483647, h; int g[257] = { 0 }; scanf("%d %d %d", &a, &b, &in); //땅의 높이가 같은것 갯수 for (int i = 0; i < a;i++) { for (int k = 0; k < b; k++) { scanf("%d", &tmp); g[tmp] += 1; } } //땅의 높이가 최고인것을 max에 넣기 for (int i = 0; i < 257; i++) { if (g[i] != 0 && i > max) max = i; } //땅의 높이가 최고인것 부터 0 까지 탐색 for (int i = max; i >= 0; i--) { //sum_s=높이가 작은것의 갯수 sum_b=높이가 높은것의 갯수 inv=인벤토리 int sum_s = 0, sum_b = 0, inv = in, time = 0; for (int k = 0; k < 257; k++) { //k높이의 땅이 i높이 보다 작으면 높이차 * 땅의 갯수 == 꺼낼 블록 갯수 if (k < i && g[k] != 0) { sum_s += g[k] * (i - k); } //k높이의 땅이 i높이 보다 크면 높이차 * 땅의 갯수 == 제거할 블록 갯수 else if (k > i && g[k] != 0) { sum_b += g[k] * (k - i); } } // 블록을 꺼내는데 걸리는 시간 + 블록을 제거하는 시간 * 2 time += sum_s + sum_b * 2; //현재인벤토리 + 블록을 제거하여 얻은 블록 수 - 블록을 꺼내는데 사용한 블록 수 inv += sum_b - sum_s; //인벤토리가 음수가 아니고 시간이 작을 때 if (inv >= 0 && time < result) { result = time; h = i; } } printf("%d %d\n", result, h); return 0; } | cs |
-c로 푼사람이 적어서 그런지 1등했다
댓글 쓰기