qkqhxla1   2달 전

어느정도 가는거보니 알고리즘은 맞는거같은데... 한끗차이로 틀린거같은데 뭐가 문제일까요??

네트워크 최대유량처럼풀려고 그래프를

시작점          상어           먹을수있는상어            도착점

               /      O        ㅡ          O                   \

O          ㅡ     O        ㅡ           O                  ㅡ        O


이런식으로 모델링해서 시작점-상어의 유량은 최대 2가 갈수있다고 하고, 상어-먹을수있는상어의 유량은 1,

먹을수있는상어-도착점은 1로 유량을 가정하고 풀었습니다.

noeffserv   2달 전

제가 봤을때, 이 코드대로라면 상어1과 상어2의 능력치가 같을 경우 서로 잡아먹어서 아무도 남지 않게 됩니다. 

하지만 상어1이나 상어2 둘 중에 한마리는 살아있어야 합니다.

qkqhxla1   2달 전

감사합니다. 원인을 알았는데 방법론을 찾기가 힘드네요...

noeffserv   2달 전

능력치가 같다면 i<j 일때, capacity 에 1을 부여하면 되겠네요. 다시 말해서 능력치가 같은 상어1과 상어2가 있을때, 상어1의 인덱스가 작다면 상어2가 상어1를 못잡아 먹게 하면 될것 같습니다.

qkqhxla1   2달 전

i와 j의 능력치가 같음. i<j일때 j상어가 먹을수 있는 양을 2에서 1로 줄임.

이게 말씀하신게 맞나요..? 그런데 능력치가 같은 다른 상어의 먹는 양을 1로 줄이는것과, j상어가 i상어를 못먹게하는것과 어떤 관계가 있는지

잘 모르겠습니다. 간단하게라도 설명좀 해주실수 있나요...?;

noeffserv   2달 전

capacity [j상어 인덱스][i상어 인덱스] 에 있던 용량 1을 0 으로 없애주기만 하면 됩니다. 나머지는 그대로구요 그럼 j상어가 i상어를 잡아먹지 못하죠

qkqhxla1   2달 전

아!!!!!!!!!!!!! 정말 감사합니다!!!!

noeffserv   2달 전

77번째 줄 capacity[i+1][1000 + j+1] = 1; 에서 i >= j 일때는 capacity[i+1][1000 + j+1] = 0; 으로 바꿔주면 되겠네요 물론 상어 능력치가 같을때만요

noeffserv   2달 전

아 이미 이해하셨네요ㅋㅋ 

qkqhxla1   2달 전

정말 감사합니다 AC떴습니다

spearkkk   3주 전

감사합니다. 예외 케이스를 생각못했는데, 

서로 같은 능력치일때, 한 마리만 살아남는 것을 말해주셔서 바로 알아차렸네요.

감사합니다.

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