[백준] 1239 - 차트(Java)

문제 파악

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

풀이

주어진 N이 [1,8]로 작은 편에 속한다.
따라서 재귀로 풀이해도 문제가 없을 것으로 판단했다.

핵심 구현 사항은 다음과 같다

• 순열 배열 생성 (재귀)
• 누적 퍼센트 저장
  • 10%, 40%, 50%의 경우, [10, 50, 100] 이 저장될 것
• 누적 퍼센트를 순환하며 반대 방향의 누적 퍼센트가 있는지 탐색
  • ex. 30% -> 80%가 있는지 검사 (즉 50%를 더한 값이 존재하는지 확인)

참고) 퍼센트를 각도로 변환하게 될 시 소수점 문제가 있어서, 자연수인 퍼센트를 활용해야 한다 😅

조금 더 코드를 보완하기 위해서는 50%를 초과하는 값들은 탐색에서 제외하는 방법을 추가할 수도 있겠다.
(그 값들은 (0, 50) 구간에서 이미 판별했을 것이기 때문)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.stream.Collectors;

public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[][] status;
    private static int N;
    private static int answer;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        Map<Integer, Integer> frequencyMap = Arrays.stream(br.readLine().split(" ")).map(Integer::parseInt)
                .collect(Collectors.toMap(k -> k, k -> 1, Integer::sum));
        status = frequencyMap.entrySet().stream().map(e -> new int[]{e.getKey(), e.getValue()}).toArray(int[][]::new);
        permute(0, new int[N]);
        System.out.println(answer);
    }

    private static void permute(int count, int[] arr) {
        if (count == N) {
            answer = Math.max(answer, countLines(arr));
            return;
        }
        for (int i = 0; i < status.length; i++) {
            if (status[i][1] == 0) {
                continue;
            }
            status[i][1]--;
            arr[count] = status[i][0];
            permute(count + 1, arr);
            status[i][1]++;
        }
    }

    private static int countLines(int[] percentageArr) {
        HashSet<Integer> cumulativePercentageSet = new HashSet<>();
        int cumulatePercentage = 0;
        for (int percentage : percentageArr) {
            cumulatePercentage += percentage;
            cumulativePercentageSet.add(cumulatePercentage);
        }
        int count = 0;
        for (int cp : cumulativePercentageSet) {
            if (cumulativePercentageSet.contains(cp + 50)) {
                count++;
            }
        }
        return count;
    }
}