알고스팟 알고리즘: 록 페스티벌(FESTIVAL) [C++]

문제 출처: https://algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

1. 코드

#include <iostream>

using namespace std;

double min_cost = 0;
int N, L;               //N: 공연장을 빌릴 수 있는 날, L: 섭외한 공연팀의 수
int * arr;              //날마다 생기는 비용(동적할당)

//문제 해결을 위한 재귀 함수
void solution(int cur, int cnt)     //cur: 현재 배열의 위치, cnt: 추가적으로 더하는 수치
{
    double temp = 0;
    for(int i = cur; i < L + cnt; i++)
        temp += arr[i];
    
    temp /= (L + cnt) - cur;        //날마다 발생하는 평균 계산
    
    if(min_cost > temp)
        min_cost = temp;
    
    if(L + cnt < N)         //더할 수 있는 범위가 남아있다면
        solution(cur, cnt + 1);
    else if(cur < N - L)    //추가적으로 탐색이 가능하다면
        solution(cur + 1, cur + 1);
}

int main(void)
{
    cout.setf(ios::fixed);  //소수점 자리 고정
    cout.precision(11);     //소수점 이하의 갯수를 11자리로 설정
    
    int C;      //테스트 케이스 횟수
    cin >> C;
    
    while(C--)
    {
        cin >> N >> L;
        arr = new int[N];
        for(int i = 0; i < N; i++)      //날마다 비용 입력
        {
            cin >> arr[i];
            min_cost += arr[i];         //최대한 큰 값으로 만들기 위해
        }
        solution(0, 0);
        
        cout << min_cost << endl;
        delete [] arr;
    }
    return 0;
}

(실행)

2. 풀이

문제를 해결하기 위한 방법으로 재귀를 이용하여 구할 수 있는 평균의 수를 구하여 비교하는 방법을 생각했다. 만약 공연장을 빌릴 수 있는 날이 총 6일이고, 비용이 1, 2, 3, 1, 2, 3이라고 가정했을 때 아래와 같이 수를 더한다.

첫 번째 위치에서 시작되는 경우

두 번째 위치에서 진행되는 경우

세 번째 위치에서 진행되는 경우

네 번째 위치에서 진행되는 경우

그리고 더한 값을 진행된 날 만큼 나누고 해당 수들 중 가장 작은 수를 출력하면 된다.

int main(void)
{
    cout.setf(ios::fixed);  //소수점 자리 고정
    cout.precision(11);     //소수점 이하의 갯수를 11자리로 설정
    
    int C;      //테스트 케이스 횟수
    cin >> C;

예제를 보면 알겠지만 소수점 이하의 수가 11개이므로 setf에서 fixed와 precision(11)을 이용하여 출력 시 소수점 이하의 수가 11자리까지 나오도록 출력을 해준다.

while(C--)
{
    cin >> N >> L;
    arr = new int[N];
    for(int i = 0; i < N; i++)      //날마다 비용 입력
    {
        cin >> arr[i];
        min_cost += arr[i];         //최대한 큰 값으로 만들기 위해
    }
    solution(0, 0);
        
    cout << min_cost << endl;
    delete [] arr;
}

반복문을 이용하여 테스트 케이스 입력 횟수(C)만큼 반복을 진행하며 공연장을 빌릴 수 있는 날(N)과 섭외한 공연팀의 수(L)을 입력해준다. 그리고 날마다 발생하는 비용을 저장하기 위해 N만큼 동적할당을 진행합니다. 날마다 발생하는 비용을 입력 후 재귀 함수를 통해서 구한 가장 작은 비용을 출력 후 동적할당을 해제한다.

//문제 해결을 위한 재귀 함수
void solution(int cur, int cnt)     //cur: 현재 배열의 위치, cnt: 추가적으로 더하는 수치
{
    double temp = 0;
    for(int i = cur; i < L + cnt; i++)
        temp += arr[i];
    
    temp /= (L + cnt) - cur;        //날마다 발생하는 평균 계산
    
    if(min_cost > temp)
        min_cost = temp;
    
    if(L + cnt < N)         //더할 수 있는 범위가 남아있다면
        solution(cur, cnt + 1);
    else if(cur < N - L)    //추가적으로 탐색이 가능하다면
        solution(cur + 1, cur + 1);
}

반복문을 이용해 정해진 지점부터 정해진 범위까지 더하여 평균값을 구한 뒤 평균 비용들 중 가장 작은지 확인 후 더할 수 있는 범위가 남아있다면 범위를 늘리고 그렇지 않다면 추가적으로 더 탐색이 가능한지 확인 후 탐색을 진행한다.

solution 함수는 탐색이 가능한 범위가 존재하지 않을 때까지 반복하며 반복이 끝나면 최소 비용이 무엇인지 정해져서 문제를 해결할 수 있다.

3. 느낀점

오랜만에 재귀를 이용한 브루트 포스 방식으로 코드를 짜서 조금 힘들긴 했지만 해결하고 나니 생각보다 어려운 문제는 아니였고, 다음에 봤을 때도 쉽게 해결할 수 있을 것 같다. 그런데 왜 인지는 모르겠지만 vector를 사용하면 문제에서 틀렸다고 나와서 동적할당을 이용하였더니 문제가 해결되었다. 아무래도 vector의 구조에 대해서 자세히 몰라서 이유는 모르겠지만 나중에 vector에 대해서 알아보아야겠다.