lian   8년 전

아무리 읽어봐도

출력값이 이상한데요.

1 2 1

1 3 2

2 3 3

1 2 1

1 4 2

2 3 3

2 4 4

3 4 1

여기서 두번째 케이스의 경우가 4번째 줄인 1 2 1 에서 시작하는데요

이 두번째 케이스의 2번째줄(전체 출력부분에서 5번째줄)에 해당하는 곳을 보면요...

"1 4"가 서로 만나는 session에 있을 때

그 바로 밑에줄에 나오는 "2 3"도 서로 만나는 session을 열어서 두 세션이 모두 한 slot에 있을 수 있다고 생각하거든요?

그러니까 4번째줄 부터는

1 2 1

1 4 2

2 3 2

2 4 3

3 4 1

이렇게 출력되야 맞는거 아닌가요??

제가 문제를 잘못이해한건지... 답변 부탁드릴게요.


ㅠㅠ

leejk9592   5년 전

스페셜 저지라 답이 여러개 일 수 있습니다.

두번째 케이스의 경우
1은 (2, 4)
2는 (1, 3, 4)
3은 (2, 4)
4는 (1, 2, 3)
과 묶이고, 모르는 회원이 가장 많은 2, 4번 회원이 3명의 회원을 모르므로 (3 + 1) = 4까지 세션을 사용할 수 있습니다.

문제의 출력 예시의 경우 속편하게 1 ~ 4 세션을 모두 쓴 경우고, 
질문자님의 출력 예시도 정답이 될 수 있겠습니다.

k = 모르는 회원이 가장 많은 회원의 모르는 회원 수

(질문자님의 출력 예시처럼 k개의 세션만 사용해서 정답을 찾는 문제는 NP-Hard 문제이고,
k + 1개의 세션을 사용해서 정답을 찾는 경우는 다항 시간복잡도 문제라고 하네요)

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