[백준] 1239: 차트 - JAVA

https://www.acmicpc.net/problem/1239

 

풀이

원형 차트를 만들 때, 각 구간의 비율이 주어진다.

 

각 구간을 적절히 배치했을 때 원의 중심을 지나는 선의 개수를 최대로 해야한다.

 

어떤 구간합이 50이 되면 원의 중심을 지나는 선이 생긴다.

 

순열을 만들어 각 구간들을 어떻게 배치할지 정했다. 이때, set을 이용해 중복제거를 해줬다.

 

구해진 순서를 슬라이딩윈도우 방식으로 구간합이 50이 되는 개수를 찾아 정답을 갱신해줬다.

 

---

 

메모리: 49480KB
시간: 416ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    static int n, answer;
    static int[] arr, selected;
    static boolean[] visited;
    static Set<String> set;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            if (arr[i] > 50) {
                System.out.println(0);
                return;
            }
        }

        answer = 0;
        visited = new boolean[n];
        selected = new int[n];
        set = new HashSet<>();
        makeGroup(0);

        System.out.println(answer);
    }

    private static void makeGroup(int idx) {
        if (idx == n) {
            if (!set.contains(Arrays.toString(selected))) {
                calc();
            }
            set.add(Arrays.toString(selected));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                continue;
            }
            selected[idx] = arr[i];
            visited[i] = true;
            makeGroup(idx + 1);
            visited[i] = false;
        }
    }

    private static void calc() {
        int cnt = 0;

        int left = 0;
        int right = 0;
        int sum = 0;
        while (right < n) {
            if (sum < 50) {
                sum += selected[right++];
            } else if (sum == 50) {
                cnt++;
                sum += selected[right++];
            } else {
                sum -= selected[left++];
            }
        }

        answer = Math.max(answer, cnt);
    }

}