SWEA 18799. 평균의 평균

주어진 서로 다른 n개의 정수로 구성된 집합에 대해서 공집합이 아닌 부분집합의 평균의 평균을 구하는 문제이다.

 

n<=8 로 충분히 작기 때문에 백트래킹을 수행하면서 공집합이 아닐 때, 현재 합 / 길이 를 계산 후 저장한다.

private static void backtracking(List<Double> list, int[] numbers, int sum, int count, int start) {
    if(count != 0) {
        list.add((double)sum /count);
    }
    for(int i=start; i<numbers.length; i++) {
        backtracking(list, numbers, sum+numbers[i], count+1, i+1);
    }
}

 

 

백트래킹 수행 후 나온 평균들의 평균을 출력하면 된다.

List<Double> list = new ArrayList<>();
backtracking(list, numbers, 0, 0, 0);
double sum = 0;
for(double average: list) sum += average;
sb.append(sum / list.size()).append('\n');

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] numbers = new int[n];
            for(int i=0; i<n; i++) numbers[i] = Integer.parseInt(st.nextToken());
            List<Double> list = new ArrayList<>();
            backtracking(list, numbers, 0, 0, 0);
            double sum = 0;
            for(double average: list) sum += average;
            sb.append(sum / list.size()).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static void backtracking(List<Double> list, int[] numbers, int sum, int count, int start) {
        if(count != 0) {
            list.add((double)sum /count);
        }
        for(int i=start; i<numbers.length; i++) {
            backtracking(list, numbers, sum+numbers[i], count+1, i+1);
        }
    }
}