[백준 BOJ] 14889번 - 스타트와 링크 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

삼성 SW 역량 테스트 기출 문제

14889번: 스타트와 링크 | 문제 바로가기

문제풀이 (2022-01-30 SUN 💻)

⭐ 풀이의 핵심

next_permutation을 활용해서 풀 수도 있는데

cf) next_permutation을 활용하여 조합 구하기
👉 https://twpower.github.io/90-combination-by-using-next_permutation

재귀는 매번 써도 매번 새롭고.. 헷갈리는 부분들이 꼭 등장하기 때문에..
나는 DFS 방식으로 재귀를 활용하여 풀어보았다

팀을 무조건 두 팀으로 나누는 것이므로
한 팀을 뽑으면 다른 팀은 알아서 구성된다는 점을 염두에 두고 풀면 된다

🚨 간과 또는 실수한 부분

팀별 능력 치 값을 계산하는 부분 (아래 코드에서 calculateSkill 함수) 에서
처음에 조건문을 아래와 같이 짜는 실수를 저질렀다..
테케 답이 이상하게 출력되길래 바로 알아챘지만..!

if (selected[i] && selected[j]) {
	skillA += S[i][j];
}
else { // 추후 이 부분을 else if (!selected[i] && !selected[j]) 로 수정함
	skillB += S[i][j];
}

+) 실수한 부분은 아닌데, 다 풀고 구글링 하면서 다른 풀이들 구경하다가 얻은 팁!
최솟값 구하는 변수 (아래 코드에서 minDiff 변수) 큰 값으로 초기화 해줄 때
맥시멈 값 계산하기는 귀찮고 뭔가 int 범위 내의 변수인 것은 확실할 때
2147483647로 초기화 하는 게 좋다는 꿀팁을 얻었다 !

🔽 코드 (C++)

#include <iostream>
using namespace std;

int N;
int S[20][20];
int selected[20] = {0, };
int minDiff = 99999999;

void calculateSkill() {
    int skillA = 0; // A팀(selectTeam 함수에서 뽑힌 사람들로 구성)의 능력 치
    int skillB = 0; // B팀(나머지 사람들로 구성)의 능력치

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (selected[i] && selected[j]) {
                skillA += S[i][j];
            }
            else if (!selected[i] && !selected[j]) {
                skillB += S[i][j];
            }
        }
    }

    int diff = skillA >= skillB ? skillA - skillB : skillB - skillA;
    if (diff < minDiff) {
        minDiff = diff;
    }
}

// 두 팀으로 나누는 것이므로 한 팀을 다 뽑으면 다른 팀은 알아서 구성됨
void selectTeam(int count, int idx) { // count: 뽑힌 사람의 수, idx: 다음 탐색 시작 값
    if (count == N/2) { // N/2명으로 이루어진 팀이 나누어진 경우
        calculateSkill(); // 각 팀의 능력치 계산 후 능력치 차이의 최솟값 업데이트
    }

    for (int i=idx; i<N; i++) {
        selected[i] = true;
        selectTeam(count+1, i+1);
        selected[i] = false; // 복원
    }
}

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

    selectTeam(0, 0);

    printf("%d", minDiff);
    
    return 0;
}