SW 역량테스트 - [백준] 스타트와 링크 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/14889

해답 코드 : 

 

#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int map[20][20];
int p_sum[20][20];

// divide team to 'start' and 'link'
// 0 : 'start', 1 : 'link'

int divide[20];

int ans;

// compute difference, using divide[20]
void compute_diff() {

	int st_sum = 0;
	int lk_sum = 0;

	/*
	vector<int> start;
	vector<int> link;

	for (int i = 0; i < N; i++) {
		if (divide[i] == 0) {
			start.push_back(i);
		}
		else {
			link.push_back(i);
		}
	}

	// calculate st_sum
	for (int i = 0; i < (N / 2) - 1; i++) {
		for (int j = i + 1; j < N / 2; j++) {
			st_sum += p_sum[start[i]][start[j]];
			lk_sum += p_sum[link[i]][link[j]];
		}
	}
	*/
	
	for (int i = 0; i < N-1; i++) {
		for (int j = i+1; j < N; j++) {
			if (divide[i] == 0 && divide[j] == 0) {
				st_sum = st_sum + p_sum[i][j];
			} else if (divide[i] == 1 && divide[j] == 1) {
				lk_sum = lk_sum + p_sum[i][j];
			}
		}
	}
	

	ans = min(ans, abs(st_sum - lk_sum));

}

// divide team into 'start' and 'link'
// # of 'link' members = cnt
void make_team(int x, int cnt) {

	if (ans == 0) return;

	if (cnt == N / 2) {
		compute_diff();
		return;
	}

	for (int i = x; i < N; i++) {

		if (divide[i] == 1) continue;

		// mark 'link'
		divide[i] = 1;
		make_team(i, cnt + 1);
		// restore
		divide[i] = 0;

	}

}


int main() {

	ans = INT32_MAX;
	fill(divide, divide + 20, 0);

	cin >> N;


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < N-1; i++) {
		for (int j = i+1; j < N; j++) {
			p_sum[i][j] = map[i][j] + map[j][i];
		}
	}

	make_team(0, 0);

	cout << ans;

	return 0;
}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제