noeffserv   1년 전

조건이해가 잘 안됩니다.


문제 내용에서 위원회를 구성하는 조건 중...

1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다.

라는 조건이 있는데.. 이 조건대로라면..


1번과 2번이 알고있고

2번과 3번이 알고 있으면

2번은 위원회 1개 혹은 2개를 가질 수 있는거 맞죠?


2번이 위원회를 1개 가질경우)

위원회1 {1,2,3}


2번이 위원회를 2개 가질경우)

위원회1. {1,2}

위원회2. {2,3}


근데 제 느낌상으론

첫번째 경우가 맞는것 같은데.. 만약에 첫번째가 맞다면 도저히 왜 틀리는지를 모르겠네요.ㅠ

{1,2}, {2,3} 의 경우는 불가능합니다.

서로 알고 있는 사람은 반드시 같은 위원회에 속해야 하기 때문에, 1은 2와 반드시 한 팀, 3도 2와 반드시 한 팀이 되어야 해서

{1,2,3}의 경우만 가능합니다. 1과 3은 서로 모르지만 각자 2와 한 팀이어야 해서 결과적으로 한 팀을 이룹니다.

혹시 사이클로 푸셨다면, 아는 사람이 한 명도 없는 사람이 단독 위원회를 잘 구성하고 있는지 확인하실 필요가 있을 듯해요

noeffserv   1년 전

예제를 돌려보니

단독 위원회는 잘 나오는것 같더라구요.

그래도 한번 확인은 다시 해볼게요.

제가 본문 글처럼 두가지 경우로 생각한 이유가 뭐냐면..

www.jungol.co.kr 에서

코드를 돌려보고 틀린 input 과 output 일부를 확인해보니깐

답이 너무 이해가 안되게 나와서요.


아래 케이스의 답으로 jungol 저지에서는

가능한 위원회 수가 100개 라고 뜨는것 같습니다.


input:

100

113

48 93

69 5

26 71

48 98

29 44

36 21

64 99

50 87

62 100

75 60

83 84

53 54

38 18

63 28

34 32

71 45

12 91

97 16

31 30

65 88

14 100

78 18

93 39

13 47

28 21

80 78

28 29

24 37

96 18

43 82

60 98

55 50

64 49

46 99

75 9

11 1

99 30

56 67

33 3

85 73

63 82

31 51

39 67

17 62

82 40

85 20

20 32

43 89

39 92

96 17

43 29

82 36

75 19

60 37

84 50

15 46

42 51

19 41

43 44

81 89

53 34

58 91

56 77

28 82

94 24

38 14

66 8

51 52

14 86

27 17

73 7

91 57

25 9

69 6

11 79

98 87

13 90

24 61

13 92

3 23

56 95

92 66

68 53

86 100

55 2

7 79

73 11

69 67

84 10

17 78

89 44

35 17

78 86

37 3

80 27

87 12

54 7

93 30

12 88

97 19

46 70

85 34

11 34

31 71

68 32

44 22

32 1

74 66

76 88

36 40

64 72

4 55

9 59

Cpu: 100 ((이 부분입니다. output 이 아닌걸까요?))

4

-----------------

Your: 4

17

=================


그런데 본문의 첫번째 경우처럼 생각했을 때, 제 코드론 4개의 위원회 밖에 나오지가 않습니다..

참.. 휴..

어쨌든, 도움주셔서 감사합니다.


제 코드에서도 위 케이스가

4

11

29

78

98

이 나오네요

테스트 케이스가 부족해서 우연히 맞았던 걸까요 ㅋㅋㅋ

noeffserv   1년 전

결과 올려주셔서 감사합니다.

제가 잘못한 부분이 있는걸 확인했습니다.

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