dwhylee   7년 전

접근이 틀렸는지 궁금해서 질문 올립니다.

일단 방에 최대한 많이 들어가야하니까, 가장 적은 소가 원하는 방을 먼저 채우는게 key로 생각하여(방을 많이쓰는게 목적이니까)

sort 한 후,  적은 것 부터 처리해 주되, 소가 방에 아직 안들어간 경우에만 들어갈 수 있게 하였고,

같은 방을 원하는 경우, 자신이 더 갈수있는 곳이 적은 소를 그쪽으로 보내는 전략을 써서 작성했는데 (더 많이 갈수있는 소는 다른 방 갈 수 있는가능성이 높다고 생각)

몇일동안 틀렸다고 나와서 질문 올려봅니다.

3 3
1 1 2 3              => 1번방은 1번소 하나  , 2번방은 2번소, 1번소  두개     3번방은    3번소, 2번소, 1번소   이렇게 정
2 2 3
3 3     으로 볼 떄 1번 소가 1번방으로 먼저 간 후 , 2번소가 2번방, 3번소가 3번방으로 들어가게 되는데

다르게 생각한 것은 소가 원하는 방이 적은 애들부터 먼저 해주는 것도 해봤는데 이게 두 생각이 조금 섞인거 같아 혼잡해져서 정리가 안되네요.

sksdong1   7년 전

해보셔서 아시겠지만 그리디하게 해서는 안풀리구요

이분 매칭이나 네트워크 플로우 알고리즘을 찾아보세요

dwhylee   7년 전

그리디로 안풀리는 예가 있을까요?

처음에 접근할 때 그리디로 안풀린다는것은 어떻게 알아야할지도 궁금합니다 ㅜㅜ

dwhylee   7년 전

@baekjoon 밑에 질문 설명 해주실 수 있으신가요? ㅠㅠ..

comseung18   3년 전

3 3

1 1 3

2 1 2

3 1 2


위와 같은 상황 일 때,  각자 갈 수 있는 방의 개수가 2개라서 

1 번이 3 번 방이 아니라 1번방을 가는 순간,

2번과 3번은 2번방을 가서 답이 3이 아니라 2가 나오게 됩니다.


그러니 갈 수 있는 방이 같은 경우에는 누가 먼저 고를지 알아야 할 것 같네요.

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