외계인 명수와 종족수에 관련된 문제인데
외계인 집단 n명이 있음, 그리고 그 집단의 종족 종류가 있음
외계인은 같은 종류끼리 한번씩 싸움
예를들어 외계인 집단이
a a a b b c d 이런 식으로 있으면 외계인 7명 4종족이 있는거고
a에서 3번, b에서 1번 싸워서 총 4번 싸우는거
여기서 풀어야할 문제는 외계인 n명, 그 외계인 들이 총 싸운 횟수 m번을 입력값으로 줌
그럼 가능한 종족수의 최소, 최대값을 출력해야함
이문제를 1시간 넘게 풀려고 햇는데 결국 못풀고
아직도 기억나는데 인터넷에 검색해도 쥐뿔도 안보이네
풀이법 아이디어 라던가, 해당 문제 링크 아는사람 있으면 도움 부탁 드림
걍 대충 문제 보고 생각했을 때 니가 올린 aaa bb c d 에서 a에서 3번 b에서 1번 싸운다는 말은 각 종족에서 2가지 뽑는 조합의 수랑 같으니까
싸운횟수 m을 입력값 받았고, 어떤 종족에 속한 애들이 x마리라고하면 xC2 = x(x-1)/2 가 되는데 이게 m이랑 매우매우매우 가까워져야 종족의 토탈 수가 적어지겠지? 그래서 x(x-1)/2 =m 이라는 이차방정식 풀어서 x에 floor 함수 취했을 때(가우스 기호로 [x]) 그게 가장 마릿수가 많은 첫번째 종족이 될테고, 그 [x]([x]-1)/2 를 계산해서 m이랑 차이나는거만큼 다시 같은 알고리즘 반복하면 종족의 토탈 수가 적게끔 세팅 가능
반대로 종족의 수가 가장 크려면 애새끼들을 두마리씩 짝짓는 경우가 가장 많아야하니까 [n/2]로 계산해본 다음에 m이랑 차이 생각해서 3마리 들어있는 종족 끼워야하면 끼우고 뭐 이런식으로 해서 m에 맞게끔 종족 넣으면 되겠찌
내생각이랑 아이디어는 비슷하네. 결국 while if문 반복 해야하는거 같은데 함 노가다 해봐야겠네 땡큐