junsoopooh   3년 전

66163905 

66063088

제출이 정답처리 되는데, 반례를 발견했습니다. 가장 낮은 케빈 베이컨 수를 가진 사람보다 앞에서 2번째로 낮은 케빈베이컨 수를 가진 사람이 다수일 경우 잘못된 답이 나옴에도 정답처리 됩니다.

데이터

6 8
1 2
2 3
3 4
4 5
5 6
6 1
6 2
6 3

그려서 계산해보면 다음과 같습니다.

사람 번호123456합
101

2

3219
210

1

2217
32101217
43210129
52221018
61112106

결과적으로 6번이 가장 작은 케빈 베이컨 수를 가집니다만 3이 출력됩니다.

출력 : 3

정답 : 6

gnzpstly2000   3년 전

첫번째 데이터는 그려보면 1과 5가 베이컨 수 7로 동일해서 낮은 수를 출력해야하니 정답이 1인것 같은데 왜 5인가요??

junsoopooh   3년 전

아고 데이터가 잘못됐네요 수정하겠습니다 ㅠ

startlink   3년 전

재채점했습니다.

ehehfdlvy4   1년 전

감사합니다 덕분에 오류를 찾았습니다!

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