백준 14899 (삼성 SW 역량평가 기출) - 스타트와 링크

 이 포스팅은 삼성 GIST 모터 트랙 대비 과정에서 풀었던 기출 문제에 대한 글입니다. 모두 백준에 공개된 문제들만 있으며, SW Expert Academy에서만 다루는 문제들은 저작권 문제로 업로드 되지 않습니다.

---

1. 문제 내용

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

문제 난이도: SILVER 1

2. 접근법

• N명을 반반으로 나누는 경우의 수 중 점수가 최소인 경우를 구하는 문제. 즉, 조합 문제임.

• 한 번 조합을 나누고 나면 그 조합의 점수 계산은 O(N^2)(2차원 배열을 흝으며 더해야 하기 때문).하지만 N이 20이하라 간에 기별도 안 감. 걱정 없이 반으로 나누는 경우의 수 훑기만 집중하면 됨.

• 조합을 이용해서 풀거나, 경우의 수이므로 백트래킹으로 풀 수 있음. 아래 풀이는 백트래킹으로 푼 내용.

3. 풀이 코드

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int N;
int mn = INT_MAX;
int s[20][20];
bool visited[20] {false, };

// end condition 도달 시 점수 계산 및 최소값 갱신
void calculateScore() {
    int start_score = 0;
    int link_score = 0;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(visited[i] && visited[j]) start_score += s[i][j];
            else if(!visited[i] && !visited[j]) link_score += s[i][j];
        }
    }
    mn = min(mn, abs(start_score - link_score));
}

// 백트래킹 함수
void solve(int step, int cur) {
    if(step == N / 2) { // terminate case
        calculateScore();
        return;
    }
    
    //avg case
    for(int i = cur; i < N; i++) {
        visited[i] = true;
        solve(step + 1, i + 1);
        visited[i] = false;
    }
}


int main() {

    //io가속
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    //input
    cin >> N; 
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> s[i][j];
        }
    }
    
    //solve
    solve(0, 0);
    cout << mn << '\n';
    return 0;
    
}

4. 중요 포인트

• 백트래킹 문제를 풀 때는 재귀 호출 시 정확히 어떤 인수를 넘겨줘야 하는지 주의할 것.

//input
    ...
    //avg case
    for(int i = cur; i < N; i++) {
        visited[i] = true;
        solve(step + 1, i + 1); // <- 여기서 i 말고 cur 썼다가 1시간은 날려먹은 듯
        visited[i] = false;
    }
    ...

• 복잡도만 보고 배제하지 말고 항상 범위 확인. 특히 백트래킹의 경우 naive한 풀이 자체의 복잡도가 O(N!)이라 N이 3자리로 작게 바운드되는 경우가 많으므로 O(N^3) 까지는 포함해도 됨.