gxxhxx0224   1년 전

## 정답

```

static long solve(){
    <i>makeSet</i>();
    Collections.<i>sort</i>(<i>roads</i>);

    long totalCost=0;
    int cnt=0;
    int max=Integer.<i>MIN_VALUE</i>;
    for(Road now:<i>roads</i>){
        int from=now.from;
        int to=now.to;
        int cost=now.cost;

        if(<i>union</i>(from,to)){
            totalCost+=cost;
            cnt++;
            max=Math.<i>max</i>(max,cost);
            //모든 집을 최소비용으로 연결한 것 - 가장 비싼 간선 1개 제거
            //-> 트리가 2개의 컴포넌트로 분리됨=두개의 연결된 마을
            if(cnt==<i>n</i>-1) break;
        }
    }
    return totalCost-max;
}

```


## 오답

```

static long solve(){
    <i>makeSet</i>();
    Collections.<i>sort</i>(<i>roads</i>);

    long totalCost=0;
    int cnt=0;

    for(Road now:<i>roads</i>){
        int from=now.from;
        int to=now.to;
        int cost=now.cost;

        if(<i>union</i>(from,to)){
            totalCost+=cost;
            cnt++;

            //모든 집을 최소비용으로 연결한 것 - 가장 비싼 간선 1개 제거
            //-> 트리가 2개의 컴포넌트로 분리됨=두개의 연결된 마을
            if(cnt==<i>n</i>-2) break;
        }
    }
    return totalCost;
}


```


어차피 Road는 cost를 기준으로 오름차순 정렬이니, 

n-1개를 다 구하고 max를 빼주나 n-2개만큼만 하거나 동일해야 하지 않나요?

97%에서 틀리는데 gpt, claude는 n-2개만큼만 하면 max를 빼주지 못할 수 있다고만 말하고 반례를 전혀 들지 못합니다.

doju   1년 전

N = 2일 때의 동작을 생각해 보세요.

댓글을 작성하려면 로그인해야 합니다.