백준 14889번 : 스타트와 링크 (JAVA) 문제 풀이

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

---

---

 

문제 분석

체크해야 할 것

• 예를 들어, 4명의 선수를 팀 A, B 로 나눴을 때 -> 모든 경우의 팀 구성을 구한 뒤, 그 팀의 능력치를 다 더해서 차이가 가장 작은 값을 출력 하면 된다.
• 차이가 0이 되면 더이상 다른 경우의 수를 따져보지 않아도 된다. (시간 복잡도 줄이기)

 

팀 정하기

• 선수 1, 2, 3, 4가 있다고 하면, 각 팀에는 2명 씩 나누면 된다. 
  • 예를 들어, 팀 A에 선수(1, 2)가 있으면, 자동으로 나머지 팀 B에는 (3, 4)가 들어가는 것이다. 

1, 2, 3, 4 중에 팀 A 에 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 이런 식으로 가능하다. 팀 B 는 자동으로 나머지 선수들이 되므로, 종료 조건에서  따로 처리해주면 된다.

 

그럼 재귀 함수를 구현할 때, 반복문은 모든 선수의 절반 횟수만 돌면서 depth 를 1씩 추가하면서 재귀 호출 하면 되겠다.

이번에도 팀을 사용했는지 체크하는 boolean[] isUsed; 를 사용할 것이다.

int[] team_star = new int[N/2];		// Star 팀
int[] team_link = new int[N/2];		// Link 팀
boolean[] isUsed = new boolean[N];	// 선수 사용 여부

 

 

재귀 함수 구현

private static void dfs(int index) {
    
    /* 종료 조건 */
    if (index == N / 2) {       // index가 N/2가 되면 종료!
        int idx = 0;
        for (int i = 0; i < N; i++) {
        
        /* 나머지 선수들 link팀에 넣기! */    
            if (!isContains(i)) {   // star팀이 아닌 멤버만 link팀에 추가!
                team_Link[idx++] = i;
            }
        }

        check_team_stat();      // 팀의 능력치 차이 최소 값을 구하는 메소드 호출!
        return;
    }

    for (int i = 0; i < N; i++) {
        if (!isUsed[i]) {       // 방문 안한 i만
            isUsed[i] = true;
            team_star[index] = i;   // 먼저 star팀에 넣어준다. 재귀의 depth가 index가 된다.
            dfs(index + 1); // 다시 다음 멤버를 뽑기 위해 재귀 호출
            for (int j = i + 1; j < N; j++) {
                isUsed[j] = false;  // (1,2) 와 (2,1) 같은 중복을 피하기 위해 현재 i값 이후로만 false 처리 해준다.
            }
        }
    }
}

/* 팀의 능력치를 계산해서 최소 값을 구하는 메소드 */
private static void check_team_stat() {
    int result1 = 0;
    int result2 = 0;

    for (int i : team_star) {
        for (int j : team_star) {
            result1 += status[i][j];
        }
    }
    for (int i : team_Link) {
        for (int j : team_Link) {
            result2 += status[i][j];
        }
    }

    int n = Math.abs(result1 - result2);

    // 능력 차이가 0이면 더이상 최소 값을 구할 필요가 없기 때문에
    // 0을 출력시키고, 종료 하면 된다.
    if (n == 0) {
        System.out.println(0);
        System.exit(0);
    } else {
        // n = n >= 0 ? n : -n;
        MIN = Math.min(MIN, n);
    }
}

/* star 팀의 속한 멤버인지 체크하는 메소드  */
private static boolean isContains(int id) {
    for (int i : team_star) {
        if (i == id) return true;
    }
    return false;
}

 

 

전체 코드