BOJ[백준] - 2569 - 짐정리
https://www.acmicpc.net/problem/2569
(1) Graph로 해결하려 했는데 정렬하기 전과 정렬하고 후에 자리가 똑같은 정점(vertex)을 빼고 나머지 정점들 가지고만 MST(최소신장트리)를
만들어 볼까? 하는 생각을 했었습니다.
4 2 1 3 을 입력 받으면 정렬 했을 때, 1 2 3 4 이고 2는 그대로 있으면 되는 것이죠..
따라서 cyclic 정점 set이 (2)와 (1, 3, 4)로 분리되니 (1, 3, 4) 로만 가지고 MST를 구성해 봤습니다.
이 그림 처럼. 총 합이 9가 나오지 뭡니까 ??
이대로 끝인줄 알았습니다 ㅎ..
(2) 1 8 9 7 6 을 입력으로 받으면, 정렬 후 1 6 7 8 9 가 되고, 1은 그 자리에 있으면 되니.. (1)과 (6, 7, 8, 9)로 분리를 해서 앞서 적용한 것처럼
계산을 했더니 !?? (6+7) + (6+8) + (6+9) = 42 가 나왔습니다.
BUT!! 저 경우엔 정답이 41이네요...
1 8 9 7 6 -> 6 8 9 7 1 (1+6) -> 6 8 1 7 9 (1+9) -> 6 8 7 1 9 (1+7) -> 6 1 7 8 9 (1+8) ->
1 6 7 8 9 (1+6) = 41 입니다.
case 2번은 생각을 못하고 있었는데 결국 뛰어난 PS블로거님에게서 힌트를 얻었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 |
#include <cstdio>
#define MIN(a,b) ((a)<(b) ? (a):(b))
typedef struct vertex
{
int data, index;
} V;
const int MXN = 1000;
V a[MXN + 1];
char chk[MXN + 1];
void swap(V *v1, V *v2)
{
V t = *v1;
*v1 = *v2, *v2 = t;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i].data);
a[i].index = i;
}
// bubble sort in ascending order of a[].data
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (a[j].data > a[j + 1].data)
swap(&a[j], &a[j + 1]);
long long ans = 0;
for(int i = 0; i < n; i++)
{
if(chk[i])
continue;
int cycle = 0;
// loop 1 cycle, cycle = the # of vertices in a cycle
for(int j = i; !chk[j]; j = a[j].index)
{
cycle++;
ans += a[j].data;
chk[j]++;
}
// case 1 : check only non-sorted cyclic vertices
// 4 2 1 3 -> check (1,3,4) -> (1+3) + (1+4) = 9
// case 2 : check a vertex having minimum value in the graph and non-sorted cyclic vertices
// 1 8 9 7 6 -> check (1) and (8,9,7,6) -> (1+6) + (1+9) + (1+7) + (1+8) + (1+6) = 41
ans += MIN( (cycle-2) * a[i].data , a[i].data + (cycle+1) * a[0].data );
}
printf("%lld", ans);
return 0;
} |
cs |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
| BOJ[백준] - 1753 - 최단경로 (0) | 2017.07.14 |
|---|---|
| BOJ[백준] - 8984 - 막대기 (0) | 2017.07.13 |
| BOJ[백준] - 1316 - 그룹 단어 체커 (0) | 2017.07.13 |
| BOJ[백준] - 6223 - Cow Sorting (0) | 2017.07.13 |
| BOJ[백준] - 2593 - 엘리베이터 (0) | 2017.07.09 |
