[ALGOSPOT] 알고스팟 FESTIVAL 록 페스티벌(C++, Python)

www.algospot.com

[ALGOSPOT] 알고스팟 FESTIVAL 록 페스티벌

(C++, Python)

(글쓴날 : 2020.05.06)

 

---

* ALGOSPOT, 알고스팟 FESTIVAL 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 FESTIVAL 록 페스티벌

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

공연장을 N일 동안 대여하는데 각 날마다 드는 비용이 주어지고, 대여해야 하는 최소 날짜인 L이 주어질 때, 공연장을 하루 빌리는 데 드는 최소 평균 비용을 구하는 문제입니다.

 

저의 경우, C++와 Python을 사용했으며, 모든 경우의 수를 계산하여 비교하는 식으로 문제를 해결했습니다.

단, 주의해야 할 점이 한 가지 있는데, 문제의 출력 조건을 보면 부동 소수점 오차 범위가 존재하므로,

C++의 cout을 사용할 경우 precision() 함수를, python의 print를 사용할 경우 "%.f"등의 방식을 통해 출력할 소수점 자릿수를 명시해 주어야 합니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int dailyCost[1001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cout.setf(ios::fixed);
    cout.precision(8);
 
    int C = 0;
    cin >> C;
 
    int N = 0, L = 0;
    int day = 0;
    int rentCost = 0;
    double minRentCost = 0.0;
    while (C--)
    {
        cin >> N >> L;
        minRentCost = 987654321.0;
 
        for (int i = 0; i < N; i++)
            cin >> dailyCost[i];
 
        for (int i = 0; i <= N - L; i++)
        {
            day = 1;
            rentCost = 0;
            for (int j = i; j < N; j++)
            {
                rentCost += dailyCost[j];
 
                if (day >= L)
                {
                    if (minRentCost > rentCost / (double)day)
                        minRentCost = rentCost / (double)day;
                }
 
                day++;
            }
        }
 
        cout << minRentCost << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    N, L = map(int, input().split())
    dailyCost = list(map(int, input().split()))
    minRentCost = 987654321.0
 
    for i in range(N - L + 1):
        day = 1
        rentCost = 0
        for j in range(i, N):
            rentCost += dailyCost[j]
 
            if day >= L:
                if minRentCost > rentCost / day:
                    minRentCost = rentCost / day
 
            day += 1
 
    print("%.8f" % minRentCost)

---