글 읽기 - 시간초과 원인을 못찾겠습니다..

pl10hg 4년 전 0

질문게시판에 올라온 시간초과 게시글 참고하면서 고쳐봐도

시간초과가 계속나네요;; 원인 힌트좀 주시면 감사하겠습니다.

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

public class Main {

    static int[][] stats;
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;
    static int n;

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

        n = Integer.parseInt(br.readLine());

        stats = new int[n][n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                stats[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        divideTeam(0, 0, n);

        System.out.println(ans);
    }

    private static void divideTeam(int dept, int select, int n) {

        if (dept == n / 2) {
            getScore();
        }else {
            for (int i = select; i < n; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    divideTeam(dept + 1, select, n);
                    visited[i] = false;
                }
            }
        }
    }

    private static void getScore() {

        ArrayList<Integer> start_team = new ArrayList<>();
        ArrayList<Integer> link_team = new ArrayList<>();

        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) {
                start_team.add(i);
            } else {
                link_team.add(i);
            }
        }

        int start_score = 0;
        int link_score = 0;

        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (i == j) continue;
                start_score += stats[start_team.get(i)][start_team.get(j)];
                link_score += stats[link_team.get(i)][link_team.get(j)];
            }
        }

        int tempans = Math.abs(start_score - link_score);

        ans = Math.min(ans, tempans);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 원인을 못찾겠습니다..

pl10hg 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말