tera1130   8달 전

기본적인 결과 값은

모든 경우의 수 - (불가능한 모든 조합 수 + 불가능조합 중 중복되는 조합 수) 로 했고

불가능 조합으로 1 2, 2 3, 1 3 같은 수를 입력 받으면 불가능한 조합 중 같은 조합이 3개가 나오는 경우가 있길래

그런 경우에는 기존에 사용한 공식과 1만큼 오차가 생겨서 결과값에 1을 빼도록 했습니다.


f52985   8달 전

4 3

1 2

2 3

3 1


정답 : 0

출력 : 1


아마도 위 예시와 같이 삼각형 사이클이 생기는 경우는 처리가 잘 안되는 것 같네요

tera1130   8달 전

조합 입력 시 앞 숫자가 크면 제대로 처리가 안된것 같아서

입력 받을 때

if (temp1 >= temp2)
{
comb_list[i] = temp2;
comb_list[i + 1] = temp1;
}
else
{
comb_list[i] = temp1;
comb_list[i + 1] = temp2;
}

추가해서 수정하니 0이 나오기는 합니다. 계속 예외적인 결과가 나오니

알고리즘 자체가 잘못된것 같기도 한데... 현재 알고리즘으로도 해결 가능한건가요?

f52985   8달 전

글쎄요.. 제가 아직 이 알고리즘을 확실히 이해하지는 못해서 가능할지는 확답을 드릴 수 없겠네요.

아마 이 알고리즘으로도 해결이 불가능하진 않겠지만, 너무 정교한 계산을 요구해서 어디서 실수가 있는지를 찾기가 힘드네요..

정 안된다면 N이 200밖에 안되므로 N^3의 brute force search도 고려해보시면 좋을 것 같습니다.
다만 성공한다면 N^3짜리 알고리즘 보다는 훨씬 효율적인 알고리즘이 될거라고 생각합니다.

일단 두번째 소스코드에서는 temp1,temp2를 입력받는 부분이 누락되었는데, 여기서 입력을 받도록 고쳐도 예외 테스트케이스가 있네요.

5 3
1 2
2 5
5 1
정답 : 3
출력 : 4

tera1130   8달 전

1 2, 2 3, 3 1  처럼 수가 연속된 경우만 생각했네요.

계속 한가지 방법만 생각하니 잘 안되는 것 같네요.

brute force search도 참고해보고 다른 알고리즘도 생각을 해봐야 겠습니다.

자세한 답변 감사합니다....

tera1130   8달 전

알고리즘 새로 짰는데도 예외가 발생하는지 틀렸다고 나오네요...

이번에는 이차원 벡터로 해봤는데 왜 또 안되는지.... ㅜㅜ

이번에는 어떤 예외때문일까요?

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