[백준] 스타트와 링크 | 삼성

출처:: https://www.acmicpc.net/problem/14889

 

1. 문제 이해 및 해결과정

 1. N개 숫자중 N/2개 뽑고 =>조합

 2. 뽑은 숫자의 모든 경우의수 => 순열 을 구하고

   

 3. 스타트팀의 합 / 링크 팀의 합의 차 가 최소인 것 찾기 

 4. 다시 1번으로 돌아가 이전에 조합하지 않은 것 조합하기 

 

- 뽑은 것을 체크해두고 

- 체크된 것은(team의 인덱스 체크)  start에 더하고 체크되지 않은 것은 link에 더한다 

 

- 조합코드

 : 조합을 하면 pick에는 {1,1,0,1,0,0} 이렇게 뽑힌 것이 체크되어 있음 -> start와 link 팀 을 뽑혓으면 start에 아니면 link에 넣으면됨 

void DFS(int idx,int cnt) { //n개중 n/2개 뽑기 
	
	if (cnt == (N / 2)) {
	
		Solve();
		return;
	}

	for (int i = idx; i< N; i++) {
		pick[i] = 1;
		DFS(i + 1, cnt + 1);
		pick[i] = 0;
	}

}

 

- 순열코드

	for (int i = 0; i < N / 2; i++) { //순열 : 중복없음 순서있음 
		for (int j = i + 1; j < N / 2; j++) {
			startscore += (map[start[i]][start[j]] + map[start[j]][start[i]]);
			linkscore  += (map[link[i]][link[j]] + map[link[j]][link[i]]);
		}
	}

 

 

2. 풀이방법

  1, C++

#if 01
//스타트와 링크
//https://www.acmicpc.net/problem/14889
#include <iostream>
#include <algorithm>

#define MAXN (20)
using namespace std;

int N;
int map[MAXN + 2][MAXN + 2];
int pick[MAXN]; //팀원 뽑기
int start[10], link[10];
int sol = 0x7fffffff;
void Solve() {
	int scnt=0, lcnt = 0;

	//start (1,3,6) link에는 (2,4,5)들어감
	for (int i = 0; i < N; i++) {
		if (pick[i] == 1) { //뽑힌것 
			start[scnt++] =i;
		}
		else { //안뽑힌 것  
			link[lcnt++] =i;
		}
	}

	//팀점수계산
	int startscore = 0, linkscore = 0;
	for (int i = 0; i < N / 2; i++) { //순열 : 중복없음 순서있음 
		for (int j = i + 1; j < N / 2; j++) {
			startscore += (map[start[i]][start[j]] + map[start[j]][start[i]]);
			linkscore  += (map[link[i]][link[j]] + map[link[j]][link[i]]);
		}
	}

	sol = min(sol, abs(startscore - linkscore));

}
void DFS(int idx,int cnt) { //n개중 n/2개 뽑기 
	
	if (cnt == (N / 2)) {
	
		Solve();
		return;
	}

	for (int i = idx; i< N; i++) {
		pick[i] = 1;
		DFS(i + 1, cnt + 1);
		pick[i] = 0;
	}

}
void InputData() {
	
	scanf("%d", &N);
	for (int i = 0; i <  N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}

}
int main() {

	freopen("input.txt", "r", stdin);
	InputData();
	DFS(0,0);

	printf("%d", sol);

	return 0;
}
#endif

 2. python

#스타트와 링크
#https://www.acmicpc.net/problem/14889
import sys
sys.stdin = open("input.txt","r")

n=int(input())
board=[list(map(int,input().split())) for _ in range(n)]
team=[False]*(n+1)
minv=1e9
def dfs(t,d): #t는 선택한 팀의 개수, #d는 depth
    global minv
    if d==n:
        return
    if t==n//2: #팀의 반을 선택한 것
        #팀점수 계산
        start=link=0
        for i in range(n):
            for j in range(n):
                if team[i]==True and team[j]==True:#둘다 선택된 팀이면 start team계산
                    start+=board[i][j]
                elif team[i]==False and team[j]==False: 
                    link+=board[i][j]
        minv=min(abs(start-link),minv)
        return
    else:
        team[d]=True
        dfs(t+1,d+1)#팀을 선택한 것
        team[d]=False
        dfs(t,d+1)#팀을 선택하지 않은 것

dfs(0,0)
print(minv)

 

 

3. 오답원인

- startscore += (map[start[i]][start[j]] + map[start[j]][start[i]]); => 괄호 주의 

 

4. 알게된 점