[알고스팟] FESTIVAL 록 페스티벌 - 구현(Implementation) + 누적합(PrefixSum) JAVA

https://algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

코드설명

구현 + 누적합 을 활용합니다.

 

먼저, 이 문제를 보면, 다른 방법으로 효율적으로 풀 수 있겠다는 직감은 왔지만, 어떻게 풀어야할지 막막했습니다.

그렇기에, 먼저 주어진 로직을 주어진 로직대로 구현 했습니다.

 

해당 코드에 대한 로직입니다.

1. 초기화:
   • 각 테스트 케이스마다 최소 평균 대여 비용을 저장할 변수 answer를 매우 큰 값으로 초기화합니다. 이는 최소 값을 찾기 위한 초기 설정입니다.
2. 평균 대여 비용 계산:
   • 두 개의 중첩된 for 루프를 사용하여 모든 가능한 대여 기간 조합을 탐색합니다.
   • 바깥쪽 루프는 대여할 수 있는 최소 일수 L부터 시작하여 전체 일수 N까지 반복합니다. 이 루프는 대여 기간의 길이를 나타냅니다.
   • 안쪽 루프는 시작 일자를 0부터 N까지 반복하며, 각각의 시작점에서 대여 기간 길이만큼의 일자 동안의 비용을 합산합니다.
   • 각 조합에 대해 평균 대여 비용을 계산하고, 이전에 계산된 최소 평균 대여 비용보다 작은 경우 answer를 업데이트합니다.
3. 출력:
   • 각 테스트 케이스마다 계산된 최소 평균 대여 비용 answer를 소수점 아래 11자리까지 출력합니다.

위의 로직을 구현하며, 실수했었던 점은, contestTeamLength를 < N으로 처리했다는 점입니다. 아래코드입니다.

왜 처음에는 < N 으로 처리했는지 생각해보면, 배열의 인덱스는 0부터 시작하기에 N - 1까지만 처리하면 될 것 같다고 생각했습니다.

하지만, 해당 contestTeamLength는 "길이"를 나타내는 것이지, 배열의 인덱스를 나타내지 않습니다. 

실제로 해당 길이를 가지고서 계산하는 부분은 아래의 costSum += cost[j]에서 이미 < end로 처리하기에 길이와 배열의 인덱스 관점에서 나누어서 생각해야 합니다.

(상당히 헷갈립니다만, "공연길이"와 "배열의 인덱스" 관점에서 생각하면 알 수 있습니다.)

...
...
...
answer = 100 * 1000 + 1;
for(int contestTeamLength=L; contestTeamLength <= N; contestTeamLength++) {
    for(int start = 0; start < N; start ++) {
        int end = start + contestTeamLength;
        if(end > N || start > N) break;

        double costSum = 0;
        for(int j=start; j<end; j++) {
            costSum += cost[j];
        }

        double newAnswer = costSum / contestTeamLength;
        if(answer > newAnswer) {
            answer = newAnswer;
        }
    }
}
...
...
...

 

무료 4000ms의 초가 걸립니다.

이 문제에서는 첫 풀이문제이기에 20초까지 가능하게 해두었지만, 일반적으로 1초, 즉 1000ms 내에 문제를 해결해야 할 것 입니다.

 

한편, 누적합으로도 해결할 수 있습니다.

예를들어 문제에 주어진 1 2 3 1 2 3 을 보겠습니다.

2
6 3
1 2 3 1 2 3 
6 2 
1 2 3 1 2 3

누적합을 통해 아래의 배열을 만듭니다.

0

1

3

6

7

9

12

이렇게 연속된 숫자들을 보면, 만약 1일째부터 6일째까지의 공연비를 한번에 구한다고 하면?

12 - 0 = 12 로 바로 계산할 수 있습니다.

이전에는 6개의 배열을 모두 순회했어야 했습니다.

이 방법으로 해결할시 약 350MS 안에 해결할 수 있습니다. STRINGBUILDER를 활용하여 출력할 시 더 줄어듭니다.

 

코드로직입니다.

1. 초기화: 각 테스트 케이스에 대해 최소 평균 대여 비용을 저장할 answer 변수를 매우 큰 값으로 초기화합니다.
2. 누적합 계산:
   • cost 배열을 사용하여 prefixSum 배열을 계산합니다. prefixSum[i]는 첫 번째 날부터 i번째 날까지의 총 비용을 나타냅니다. 이를 통해 특정 범위 내의 총 비용을 효율적으로 계산할 수 있습니다.
3. 최소 평균 대여 비용 계산:
   • 모든 가능한 대여 기간에 대해 평균 대여 비용을 계산합니다. 이렇게 하기 위해, 두 개의 중첩된 for 루프를 사용합니다.
   • 바깥쪽 루프는 대여 기간(contestTeamLength)을 최소 대여 기간 L부터 총 일수 N까지 반복합니다.
   • 안쪽 루프는 대여 시작일(start)을 0부터 N까지 반복하며, 각 대여 기간에 대한 평균 대여 비용을 계산합니다.
   • 각 대여 기간에 대해, prefixSum 배열을 사용하여 해당 기간의 총 대여 비용(costSum)을 빠르게 계산하고, 이를 대여 일수로 나누어 평균 대여 비용(newAnswer)을 구합니다.
   • 계산된 평균 대여 비용이 현재 저장된 최소 평균 대여 비용(answer)보다 작다면, answer를 업데이트합니다.
4. 결과 출력: 각 테스트 케이스에 대해 계산된 최소 평균 대여 비용을 출력합니다.

 

코드를 작성하며, 실수했던 부분입니다.

 

첫번쨰, 누적합의 범위는 <=N 이다.

처음에 left + L < N 이라고 하여, 누적합은 prefixSum[N+1]의 범위인데, 마지막 N번쨰 prefixSum을 놓쳐서 모든경우를 연산하지 못했습니다.

public static double calculateMinCostAverage() {
    double ret = Double.MAX_VALUE;
    for(int left=0; left + L <= N; left++) {
        for(int right = L + left; right <= N;right++) {
            double averageCost = (double) ( prefixSum[right] - prefixSum[left] ) / (right - left);
            ret = Math.min(ret, averageCost);
        }
    }
    return ret;
}

 

두번쨰,  정수 나눗셈은 소수점 이하를 버리기 때문에 올바른 결과가 나오지 않을 수 있습니다. 이를 해결하기 위해서는 나눗셈을 수행하기 전에 피연산자 중 하나를 double로 형변환해야 합니다.

double averageCost = (double) ( prefixSum[right] - prefixSum[left] ) / (right - left);

처음에 단순히 double averageCost 로 처리하였는데, 그렇게 할경우 int 형으로 계산합니다. 즉, 7/4 = 1.0000 으로 나옵니다. 그러므로 피연산자 중 하나를 double로 형변환하여 올바르게 나눠지도록 합니다. 혹은 prefixSum 자체를 double로 선언했으면 됐습니다.

코드

무작정 구현한 코드입니다.

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int C, N, L;
	public static int[] cost; 
	public static double answer = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		for(int i=0;i<C;i++) {
			st = new StringTokenizer(br.readLine());	
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			cost = new int[N];
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				cost[j] = Integer.parseInt(st.nextToken());
			}

			answer = 100 * 1000 + 1;
			for(int contestTeamLength=L; contestTeamLength <= N; contestTeamLength++) {
				for(int start = 0; start < N; start ++) {
					int end = start + contestTeamLength;
					if(end > N || start > N) break;
					
					double costSum = 0;
					for(int j=start; j<end; j++) {
						costSum += cost[j];
					}
					
					double newAnswer = costSum / contestTeamLength;
					if(answer > newAnswer) {
						answer = newAnswer;
					}
				}
			}
			System.out.print(String.format("%.11f\n", answer));
		}
	}
}

 

누적합을 활용합니다.

package algorhythm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int C, N, L;
	public static int[] cost;
	public static int[] prefixSum;
	public static double answer = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		for(int i=0;i<C;i++) {
			answer = 100 * 1000 + 1;
			st = new StringTokenizer(br.readLine());	
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			cost = new int[N];
			prefixSum = new int[N+1];
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				cost[j] = Integer.parseInt(st.nextToken());
				prefixSum[j + 1] = prefixSum[j] + cost[j];
			}
//			for(int j=0;j<=N;j++) {
//				System.out.print(prefixSum[j]+" ");
//			}
			
			for(int contestTeamLength = L; contestTeamLength <= N; contestTeamLength++) {
				for(int start = 0; start < N; start++) {
					int end = start + contestTeamLength;
					if(end >= N + 1) break;
					double costSum = prefixSum[end] - prefixSum[start];
					
					double newAnswer = costSum / contestTeamLength;
//					System.out.println(newAnswer);
					if(answer > newAnswer) {
						answer = newAnswer;
					}
				}
				
			}
			
			System.out.print(String.format("%.11f\n", answer));
		}
	}
}

 

 

누적합 활용하며 가장 깔끔하게 푼 코드입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M, L;
	public static int answer = 0;
	public static int[] cost, prefixSum;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			cost = new int[N];
			prefixSum = new int[N+1]; // prefixSum[i+1] : cost[0]부터 cost[i]까지의 누적합. prefixSum[1]이리하면, cost[0]부터 cost[0]까지의 합을 의미한다.
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N;i++) {
				cost[i] = Integer.parseInt(st.nextToken());
				prefixSum[i+1] = prefixSum[i] + cost[i]; 
			}
			
			double answer = calculateMinCostAverage();
			System.out.println(String.format("%.11f", answer));
		}
		
	}
	
	public static double calculateMinCostAverage() {
		double ret = Double.MAX_VALUE;
		for(int left=0; left + L <= N; left++) {
			for(int right = L + left; right <= N;right++) {
				double averageCost = (double) ( prefixSum[right] - prefixSum[left] ) / (right - left);
				ret = Math.min(ret, averageCost);
			}
		}
		return ret;
	}
	
}