[FESTIVAL] 록 페스티벌
개발이야기/알고스팟2022. 1. 6. 10:49
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/FESTIVAL
algospot.com :: FESTIVAL
록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체
www.algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] caches = new int[1000][1000];
int cases = scanner.nextInt();
while (cases-- > 0) {
int n = scanner.nextInt(), l = scanner.nextInt();
for (int i = 0; i < n; ++i) {
caches[0][i] = (i == 0) ? scanner.nextInt() : caches[0][i - 1] + scanner.nextInt();
}
for (int i = 1; i < n; ++i) {
for (int j = i; j < n; ++j) {
// i일부터 (j-i+1)일 연속 공연했을 때의 총 비용
caches[i][j] = caches[i - 1][j] - caches[i - 1][i - 1];
}
}
double ret = Double.MAX_VALUE;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
int len = j - i + 1;
if (len >= l) ret = Math.min(ret, ((double) caches[i][j]) / len);
}
}
System.out.printf("%.8f\n", ret);
}
}
}
|
cs |
최소 평균 비용을 알기 위해, 모든 경우의 수를 탐색해 보는 것을 고민해봤습니다.
i일부터 연속 (n-i+1)일 간의 총 비용을 구한 뒤, 최소 평균을 구하도록 되어 있습니다.
해당 요구사항은 파스칼의 삼각형과 같이 처음부터 모든 덧셈을 하는 것이 아닌 일련의 점화식을 만들면 제곱 시간안에 구해볼 수 있습니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
반응형
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [CANDLESTICK] Candlestick Charts (0) | 2022.01.06 |
|---|---|
| [KAKURO1] Kakuro I (0) | 2022.01.06 |
| [NOTE] Note (0) | 2022.01.06 |
| [MAGICPOWER] 마력 (0) | 2022.01.05 |
| [DECODE] Decoding (0) | 2022.01.05 |