fork download
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. double min_cost = 0;
  6. int N, L; //N: 공연장을 빌릴 수 있는 날, L: 섭외한 공연팀의 수
  7. int * arr; //날마다 생기는 비용(동적할당)
  8.  
  9. //문제 해결을 위한 재귀 함수
  10. void solution(int cur, int cnt) //cur: 현재 배열의 위치, cnt: 추가적으로 더하는 수치
  11. {
  12. double temp = 0;
  13. for(int i = cur; i < L + cnt; i++)
  14. temp += arr[i];
  15.  
  16. temp /= (L + cnt) - cur; //날마다 발생하는 평균 계산
  17.  
  18. if(min_cost > temp)
  19. min_cost = temp;
  20.  
  21. if(L + cnt < N) //더할 수 있는 범위가 남아있다면
  22. solution(cur, cnt + 1);
  23. else if(cur < N - L) //추가적으로 탐색이 가능하다면
  24. solution(cur + 1, cur + 1);
  25. }
  26.  
  27. int main(void)
  28. {
  29. cout.setf(ios::fixed); //소수점 자리 고정
  30. cout.precision(11); //소수점 이하의 갯수를 11자리로 설정
  31.  
  32. int C; //테스트 케이스 횟수
  33. cin >> C;
  34.  
  35. while(C--)
  36. {
  37. cin >> N >> L;
  38. arr = new int[N];
  39. for(int i = 0; i < N; i++) //날마다 비용 입력
  40. {
  41. cin >> arr[i];
  42. min_cost += arr[i]; //최대한 큰 값으로 만들기 위해
  43. }
  44. solution(0, 0);
  45.  
  46. cout << min_cost << endl;
  47. delete [] arr;
  48. }
  49. return 0;
  50. }
  51.  
Success #stdin #stdout 0s 5536KB
stdin
2
6 3
1 2 3 1 2 3 
6 2 
1 2 3 1 2 3
stdout
1.75000000000
1.50000000000