[백준 1239] 차트 - JAVA

BOJ Link

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

 

 

풀이 과정

1. N이 매우 작으므로 순열을 사용했다. (N <=8)

순열로 N개의 원소를 뽑는 모든 경우의 수를 구한다. O(8P8 = 40320)

단, 뽑은 원소의 누적합으로 배열을 구성한다.

when dep = 0,  pick[dep] = arr[i];

when dep > 0, pick[dep] = pick[dep - 1] + arr[i];

 

+ 정확히는 같은 것이 있는 순열이다. 하지만 문제 특성상

arr[] = {A1(10), B(20), A2(10)} 일 때,

pick[] = {A1,B,A2}를 뽑은 경우와 {A2,B,A1}를 뽑은 경우의 결과는 같으므로 처리하지 않았다.

답인 경우의 개수를 세야한다면 처리해야 한다.

 

또한, 중복 순열과 같은 것이 있는 순열은 다른 개념이다. 중복 순열이라면 pick[] = {A1,A1,A1}이 가능하다.

 

2. 원의 중심을 지나는 선 = 원을 이등분하는 선이다.

0%를 기준으로 10%를 채우는 선이 있다면, 대응하는 이등분 선은 60%에 위치한다.

따라서, 어떤 선에 50을 더한 값이 이등분하는 선이다.

앞에서 누적합 배열을 구성해놨으므로, arr[i]+50 = arr[j]인지 판별한다. O(n^2)

 

제출 코드

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

class Main {
    static int ans;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int pick[] = new int[N];
        boolean visited[] = new boolean[N];

        comb(0, pick, arr, visited, N);
        System.out.println(ans);
    }

    public static void comb(int dep, int[] pick, int[] arr, boolean[] visited, int N) {

        if (dep == N) {
            getAns(pick, N);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;

                if (dep == 0)
                    pick[dep] = arr[i];
                else pick[dep] = pick[dep - 1] + arr[i];
                comb(dep + 1, pick, arr, visited, N);
                pick[dep] = 0;
                visited[i] = false;
            }
        }
    }

    public static void getAns(int[] pick, int N) {
        int now = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (pick[i] + 50 == pick[j]) now++;
            }
        }

        ans = Math.max(now, ans);
    }
}