[C++] Kick Start 2018 Round A - Lucky Dip(나중에 다시)

0. [C++] Kick Start

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edf/0000000000050e1d

1. 풀이

1) 이 문제의 핵심은 다시 뽑기를 어떤 시점에 시행하느냐에 대한 것인데,

나의 경우에는 arr를 sort로 오름차순 정렬을 한 이후, arr[i]가 이전 기대값 보다 커진 시점을 전부 더해주었고, 그 이전 값들은 이전 sum의 값을 활용해주었다.

2) 사실 이 소스코드는 small dataset에서만 통과하고 large dataset은 통과하지 못했는데, 수정 하기 귀찮아 그냥 올린다.

2. 소스코드

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 46 47 48 49 50 51

#include<iostream> #include<string> #include<algorithm>   using namespace std;   float arr[20003];   float calc(const int& N, const int& K) {     float sum = 0;       for (int i = 0; i < N; i++) {         sum += (arr[i] / N);     }       for (int j = 0; j < K; j++) {         float MAX = 0;         bool find = false;         for (int i = 0; i < N; i++) {             if(!find)                 if (sum <= arr[i]) {                     MAX += (sum * i)/N;                     find = true;                 }             if (find)                 MAX += arr[i] / N;         }         sum = MAX;     }           return sum; }     int main() {     int T;     int N, K;     cin >> T;     for (int i = 1; i <= T; i++) {         cin >> N >> K;         for (int i = 0; i < N; i++) {             cin >> arr[i];         }         sort(arr, arr + N);         cout << "Case #" << i << ": ";         printf("%.6f\n", calc(N, K));     } }   Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!