[C++] 알고스팟 - FESTIVAL

문제 링크

algospot.com :: FESTIVAL

 

처음에 생각한 풀이 )

 

  첫 팀부터 시작하여 L팀을 선택하여 평균을 구한 후 다음 팀을 확인하여 이미 구한 평균보다 큰 팀이 나오면 다음 루프를 돌리면 된다고 생각했다.

 

반례 )

 

5 3

1 4 3 4 1

 

  생각한대로 구현을 하면  (1+4+3) / 3 < 4 이기 때문에 최솟값으로 8/3을 저장한 후 다음 루프를 돌지만

답인 탐색하지 않게 되는 (1+4+3+4+1) / 5이다.

 

#include <cstdio>	// scanf(), printf()
#include <algorithm>	// min()
using namespace std;
 
int main(void)
{
    int c, n, l;
    int i, j;
    double ans;
 
    scanf("%d", &c);
    while(c--){
        // a[]는 입력으로 받는 각 팀의 비용, b[]는 최솟값을 확인하기 위한 팀 비용의 합
        int teamNum, a[1000], b[1000];
	ans = 1e9;
 
        scanf("%d%d", &n, &l);
        for(int i = 0; i < n; i++)
            scanf("%d", a+i);

        for(i = 0; i <= n-l; i++){
            teamNum = l;
	        b[i] = 0;
            // 최소 팀의 합
            for(j = i; j < i+l; j++)
                b[i] += a[j];
            for(; j < n; j++){
                // 평균 이하의 팀만 추가
                // 나누기 연산 시 오차 발생 때문에 곱셈 연산 사용
                if((double)a[j]*teamNum <= (double)b[i]){
                    b[i] += a[j];
                    teamNum++;
                }
                else
                    break;
            }
            ans = min(ans, (double)b[i]/teamNum);
        }
        printf("%.11f\n", ans);
    }
    return 0;
}

 

 

풀이 )

 

  위에 반례를 통해 모두 탐색해야 된다는 것을 알게 되었으므로 완전탐색을 통해 구했다.

  

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
    int c, n, l;
    int i, j, k, sum, check;
    int teamNum, a[1000];
    double ans;

    scanf("%d", &c);
    while(c--){
        ans = 1e9;
        scanf("%d%d", &n, &l);
        for(i = 0; i < n; ++i){
            scanf("%d", a+i);
        }
        for(i = 0; i <= n-l; ++i){
            for(j = l; j <= n-i; ++j){
                sum = 0;
                for(k = 0; k < j; ++k){
                    sum += a[i+k];
                }
                ans = min(ans, (double)sum / j);
            }
        }
        printf("%.11f\n", ans);
    }
    return 0;
}

 

주의점 )

 

- 자료형 (float -> double)

- 출력 자리 수 (7자리 이상)