커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.
이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?
예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.
public class RockFestival {
/**
* 공연장 대여 비용 일별 최소 비용
* @param l 공연할 팀
* @return 일별 최소 비용
*/
public double dayPerCost(int l) {
int[] dayCost = {1, 2, 3, 1, 2, 3};
int dayCostLength = dayCost.length;
double max = Double.MAX_VALUE;
for (int i = 0; i < dayCost.length - l; i++) {
double n = 0.0d;
for (int j = 0; j < dayCostLength; j++) {
n += dayCost[j];
}
double avg = n / dayCostLength;
dayCostLength--;
if (avg < max) {
max = avg;
}
}
return max;
}
public static void main(String[] args) {
RockFestival rockFestival = new RockFestival();
System.out.println(rockFestival.dayPerCost(3));
}
}
회고.
원래 문제는 대여 가능 일수와 섭외된 팀수를 입력 받아서 해결하는것인데, 내맘대로 대여 가능 일수를 제외하고 임시로 6일로 정하여 풀었다.
어쨌든,, 생각보다 머리가 잘 안돌아가서 부끄럽지만 이 문제 푸는데 30분은 걸린것 같다.
계속 스칼라로 알고리즘을 풀다보니 재귀에 많이 익숙해져서 재귀로 풀까도 생각했었다.
푼 방식이 뭔가 썩 맘에 들지 않는다. 더 효율적이고 다 간단히 풀어보는 방법에 대해 생각해보자.