[AOJ] 알고스팟 : FESTIVAL (JAVA)

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 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밖에 되지 않습니다.

 

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.

 

 

출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

 

 

풀이

부분 합 알고리즘으로 해결할 수 있는 문제였습니다.

 

L일 이상의 연속된 요일에 대하여 비용 합을 구해야하기 때문에 1일부터 N일까지의 부분 합을 정의합니다.

부분 합은 psum[i] = psum[i - 1] + arr[i] 로 나타낼 수 있습니다.

 

그리고 연속된 요일을 구할 때, 꼭 1일부터 시작할 필요는 없으므로 1일부터 (N - L + 1)일까지를 시작점으로 잡아서 연속된 요일에 대하여 평균 비용을 구하면 됩니다.

 

참고로, 위에서 정의한 부분 합은 1 ~ i 까지의 합을 구하는 것인데, 시작점이 1이 아닌, 2, 3, 4, ... k라고 한다면, 특정 구간의 합은 psum[i] - psum[k - 1] 을 통해서 구할 수 있습니다. (k - 1)인 이유는 구간의 시작점이 k이기 때문입니다.

 

아래는 위 내용을 정리한 소스코드입니다.

 

 

소스코드

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.io.OutputStreamWriter;
	import java.util.StringTokenizer;
	public class Main {
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	StringTokenizer st;
	int T = Integer.parseInt(br.readLine());
	StringBuilder sb = new StringBuilder();
	while (T-- > 0) {
	st = new StringTokenizer(br.readLine());
	int N = Integer.parseInt(st.nextToken());
	int L = Integer.parseInt(st.nextToken());
	int[] arr = new int[N + 1];
	st = new StringTokenizer(br.readLine());
	for (int i = 1; i <= N; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	}
	int[] psum = new int[N + 1]; // 부분 합
	psum[0] = 0;
	for (int i = 1; i <= N; i++) {
	psum[i] = psum[i - 1] + arr[i];
	}
	double ans = Double.MAX_VALUE;
	// 1일 ~ (N - L + 1)일을 시작점으로 잡음.
	// 시작점과 (i + L - 1)일 까지의 평균 비용을 구함.
	for (int i = 1; i <= N - L + 1; i++) {
	double res = Double.MAX_VALUE;
	for (int j = i + L - 1; j <= N; j++) {
	double temp = (psum[j] - psum[i - 1]) / (double) (j - i + 1);
	res = Math.min(res, temp);
	}
	ans = Math.min(ans, res);
	}
	sb.append(ans + "\n");
	}
	bw.write(sb.toString());
	bw.flush();
	bw.close();
	br.close();
	}
	}

view raw FESTIVAL.java hosted with ❤ by GitHub

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.