peptidase   8달 전

우선 N개의 선분중 K개를 선택하는 경우의수는 NCK 입니다. (컴비네이션)

근데 K각형의 한변의 길이는 다른 K-1개의 변의 길이의 합보다 작아야 하므로 NCK에서 안되는 경우의 수를 빼주기로 했습니다.

선분들을 내림차순으로 정렬하고 (L1~L10) 삼각형을 만든다 가정했을때

L1이 포함된 삼각형은 L1이 가장 긴 변이므로 L2 + L3이 L1보다 크면 넘어가서 L3 + L4를 검사하고 이런식으로 쭉쭉 넘어가다가

에를들어 L6 + L7이 L1보다 작거나 같으면 L6~L10중 두개를 골라서 아무리 더해도 L1보다 작거나 같으므로 여기서 break문을 쓴뒤

처음에 구했던 NCK에서 4C2를 빼줍니다.


그리고 L2가 가장 긴 변인 삼각형에 관해서도 위의 작업을 쭉쭉하여 NCK의 경우에서 진짜 삼각형이 되는 경우 가짓수만 남게 코드를 짰는데요

틀렸다고 나오네요;; 혹시 제가 설명한 것중 틀린점이나 코드에서 잘못된부분 있으면 좀 알려주시면 감사하겠습니다.

dotorya   8달 전

50C10 = 10272278170 > 2^31 - 1로 int범위를 초과합니다.

int 대신 long long형 변수를 사용해보세요.

(result의 최대값도 저 정도이므로, 관련 변수들도 모두 long long 변수로 처리해야 합니다.)

peptidase   8달 전

답변 감사합니다.

long long으로 바꿔서 컴비네이션은 제대로 나오는것 같은데 아직도 틀렸다고 나오네요..ㅠㅠ

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