[백준] 15661번: 링크와 스타트

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

15661번: 링크와 스타트

 

 

 

#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

int graph[20][20];
int num;
int minValue=99999;

int steam[19];
int steam_size;
int lteam[19];
int lteam_size;

vector<int> vec;

void init()
{
	cin >> num;
	for(int i=0; i<num; i++)
	{
		for(int j=0 ; j<num; j++)
		{
			cin >> graph[i][j];
		}
	}
}


bool isNumInSTeam(int n)
{
	for(int i=0; i< steam_size; i++)
	{
		if(steam[i] == n)
		{
			return true; 
		}
	}
	return false;
}

void setLteamMember()
{
	int lteam_index = 0;
	for(int i=0; i<num; i++)
	{
		if(!isNumInSTeam(i))
		{
			lteam[lteam_index++] = i;
		}
	}
}

int calculateDiff()
{
	int steam_power=0,lteam_power=0;
	for(int i=0; i<steam_size; i++)
	{
		for(int j=0; j<steam_size; j++)
		{
			steam_power += graph[steam[i]][steam[j]];
		}
	}
	
	for(int i=0; i<lteam_size; i++)
	{
		for(int j=0; j<lteam_size; j++)
		{
			lteam_power += graph[lteam[i]][lteam[j]];
		}
	}
	
	return abs(steam_power - lteam_power);
}


// r은 steam의 사람 수, steam을 r명으로 했을때 나올수 있는 차이값의 최소를  minValue에 저장
void setMinDiff(int r)
{
	int temp_min;
	if(vec.size() == r)
	{
		
		for(int i=0; i<r; i++)
		{
			steam[i] = vec[i];
		}
		
		steam_size = r;
		lteam_size = num-r;
		setLteamMember();
		temp_min = calculateDiff();
		if(temp_min < minValue)
			minValue = temp_min;
			
		return;
	}
	
	int least = vec.empty() ? -1 : vec.back();
	
	for(int i=least+1; i<num; i++)
	{
		vec.push_back(i);
		setMinDiff(r);
		vec.pop_back();
	}
}


int main() {
	init();
	for(int i=1; i<num/2+1; i++)
	{
		setMinDiff(i);
	}
	
	cout << minValue;
	return 0;
}

1. 함수화

문제를 풀면서 디버깅을 할때, isNumInSteam 이라는 함수를 새로만들어 기존에 있던 코드에서 분리시키는 과정을 더했다. 확실히 분리하고 나니 디버깅을 더 편하게 했던 것 같다. 작업별로 함수를 만들어 진행하는 것의 장점을 다시 느끼게 되었다.

 

2. 함수의 실행 순서

스타트 팀과 링크 팀을 나누는데에 오류가 있어 한참을 애먹었는데, 오류가 생겼던 이유는 setLteamMember 함수가 호출되는 시점에 steam_size 가 최신화 되어있지 않아서 생긴 오류였다. 따라서 디버깅할때는 setLteamMember 함수를 steam_size 최신화문 아래에 둠으로써 쉽게 끝냈는데, 그것을 찾는 과정은 매우 오래걸렸다. 앞으로는 어떤 함수를 넣을 때 그 함수에서 사용하는 변수를 고려하여 위치를 설정해야겠다는 생각이 든다. 또한 디버깅 할때도 해당 함수의 로직 뿐만 아니라 사용하는 변수를 의심해보아야 겠다는 생각이 들었다.

 

 

최근에 푼 문제들 중에서 특히 문제는 해결하기 위해 필요한 개념이 많았던 것 같다. 문제 하나 푸는데에 볼륨도 커서 하면서도 이게 되나 싶었는데 깔끔한 방법은 아닌것같지만 문제를 해결하게 되어서 기쁘고 보람차다. 재귀함수를 통한 조합을 통하여 스타트와 링크팀을 구성한것도 생각만큼 잘 돼주어서 좋았다. 책에서 보던 방법을 직접 구현하게 된것같아 조금씩 익숙해짐을 느꼈다. 아쉬운 점은 링크팀을 만드는 방법이 조금 지저분하지 않았나 싶다. 기회가 된다면 이 부분을 고쳐서 코드를 간략화 시켜보고 싶다.