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를 빼주지 못할 수 있다고만 말하고 반례를 전혀 들지 못합니다.
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를 빼주지 못할 수 있다고만 말하고 반례를 전혀 들지 못합니다.