문제의 핵심은 제약 조건을 만족하면서 간선의 총 개수를 최소화하는 그래프를 구성하는 것이다. 단순히 직관적으로 접근하면 함정에 빠지기 쉬우므로, 수학적 분석을 통해 최적해를 도출해야 한다.

문제 분석

다음 조건을 만족하는 그래프를 구성해야 한다:

• 모든 정점의 차수는 k 이상
• 차수가 정확히 k인 정점들 사이에는 간선이 존재하지 않음
• 두 정점 사이에는 최대 하나의 간선만 존재
• 간선의 총 수를 최소화

제약 조건: 2 ≤ k ≤ 10, 2k+1 ≤ n ≤ 1000

핵심 전략: 두 집합으로 분할

최적의 구조를 찾기 위해 정점들을 두 그룹으로 나누어 분석한다:

• A집합: 차수가 k보다 큰 정점들 (고차수 집합)
• B집합: 차수가 정확히 k인 정점들 (저차수 집합)

A집합의 크기를 m이라 하면, B집합의 크기는 n-m이 된다. B집합 내의 정점들은 서로 연결될 수 없으므로, B집합의 모든 간선은 A집합으로 향하거나 A집합 내부에서 이루어져야 한다.

최소 간선 수 도출

A집합 내부의 간선 수를 inner라 할 때, 전체 차수 합의 관계로부터 다음 부등식을 얻는다:

k(n-m) + 2·inner ≥ (k+1)·m

이를 inner에 대해 정리하면:

inner ≥ max( 0, ⌈((2k+1)m - k·n) / 2⌉ )

따라서 A집합 크기 m이 결정되면, 전체 간선 수는:

edges = k(n-m) + inner

각 가능한 m 값에 대해 위 식을 계산하여 최소값을 갖는 m을 선택한다.

구성 알고리즘

최적의 m을 찾은 후, 실제 그래프를 다음과 같이 구성한다:

1. 교차 간선 배치: A집합의 각 정점에서 B집합의 모든 정점으로 균등하게 간선을 분배. 순환적으로 연결하여 분산도를 높인다.
2. A집합 내부 보정: A집합 내에서 아도 차수가 k에 미달한 정점들을 쌍으로 연결. 홀수 개 남은 경우 하나의 정점에 대해 추가 연결 수행.

구현 예시

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int n, k, arc;
int d[1005];
bool adj[1005][1005];
vector<pii> res;

void link(int u, int v) {
    res.push_back({u, v});
    d[u]++; d[v]++;
    adj[u][v] = adj[v][u] = true;
}

int estimate(int m) {
    int need = (2*k + 1)*m - k*n;
    int inner = (need > 0) ? (need + 1) / 2 : 0;
    return k*(n-m) + inner;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    
    // 최적의 A집합 크기 탐색
    int bestM = 0, minEdge = 1e9;
    for (int m = 1; m <= n; m++) {
        int cur = estimate(m);
        if (cur < minEdge) {
            minEdge = cur;
            bestM = m;
        }
    }
    
    int aSize = bestM;           // A집합: 1 ~ aSize
    int bSize = n - aSize;       // B집합: aSize+1 ~ n
    
    // A-B 간선: 순환 연결
    int ptr = 1;
    for (int b = aSize + 1; b <= n; b++) {
        for (int j = 0; j < k; j++) {
            link(ptr, b);
            ptr = ptr % aSize + 1;
        }
    }
    
    // A집합 내부: 차수 보정
    vector<int> pending;
    for (int i = 1; i <= aSize; i++) {
        if (d[i] == k) pending.push_back(i);
    }
    
    // 짝짓기
    for (int i = 0; i + 1 < (int)pending.size(); i += 2) {
        link(pending[i], pending[i+1]);
    }
    
    // 홀수 처리
    if (pending.size() % 2 == 1) {
        int last = pending.back();
        for (int i = 1; i <= aSize; i++) {
            if (i != last && !adj[i][last]) {
                link(i, last);
                break;
            }
        }
    }
    
    // 출력
    cout << res.size() << "\n";
    for (auto& [u, v] : res) {
        cout << u << " " << v << "\n";
    }
    
    return 0;
}

핵심 정리

최소화 문제에서 직관적 접근 대신, 변수 분리와 수식 전개를 통해 최적边界的 조건을 먼저 파악하는 것이 핵심이다. A집합의 크기를 매개변수로 두고 내부 간선 수를 최소화하는 방향으로 전개하면, 전체 탐색 공간이 제한되며 효율적인 해법이 도출된다.