반례입니다.

k가 돌아가는 for문의 범위를 for k in range(i+2,N): 로 바꾸었더니 맞았더라구요. 그래서 print함수로 가시적으로 보려고 돌려봤는데 k가 한번만 돌아가야 되는데 두번 실행이 되네요? 혹시 왜 그런지 설명해주실 수 있나요?? 그리고 두 번째로 k가 돌아갈 때 어떤 루트로 11이 리스트에 추가되는지도 모르겠습니다..

k의 for문과 mx.append 다음에 print()를 넣고 실행한 결과입니다.

k : 2
[8]
k : 2
[8, 11]
11

그렇게 해도 틀려야 할 것 같은데 데이터가 약한가 봅니다.

이 코드의 문제점은 j와 k가 중복이 될 수 있다는 점입니다. k를 항상 j보다 뒤쪽의 인덱스에서만 찾아야 하는데, 이 코드는 j가 i의 인덱스 +2에 도달한 후에도 k도 똑같이 그 자리부터 시작하고 있어 중복됩니다.

답변 감사합니다.

정말 죄송한데 제가 머리가 잘 안돌아 가서요..

중복되는 부분 좀 더 자세히 설명해주실수 있나요?

원본 리스트는 [1,2,5]입니다.

i가 여기서 1을 뽑고 루프를 시작합니다. 그 다음 j는 1의 다음 인덱스부터 끝까지의 리스트인 [2,5]에서 2를 뽑고 시작합니다.

k는 1의 다음 다음 인덱스부터 끝까지의 리스트인 [5]에서 5를 뽑습니다. 여기서 1+2+5=8이 mx에 추가됩니다.

j는 이제 [2,5]에서 5를 뽑습니다.

k는 1의 다음 다음 인덱스부터 끝까지의 리스트인 [5]에서 5를 뽑습니다. 여기서 1+5+5=11이 mx에 추가됩니다.

감사합니다! j가 5를 뽑으면 k는 뽑을 것이 없어야 하는데 i+2라서 여전히 5를 갖고 있기 때문이 이것을 다시 뽑는다는 말씀이신거죠? 이해가 간 것 같아요!

그런데 아직 모르겠는 부분이 있습니다...

아래 소스코드에서 제가 1번과 같은 방법으로 작성했고, 2번이 보편적인 코드인데

1번으로 했을 경우 중복이 일어난다고 말씀하셨습니다. 

k를 무조건 j보다 뒤쪽부터 탐색해야 한다고 하셨는데 j에 해당하는 인덱스에 +1을 한 곳부터 탐색하면 j보다 뒤에서 탐색하게 되지 않을까요? 

마지막으로 답변 부탁드립니다!

이렇게 하면 리스트 자체가 중복된 원소가 여럿 있을 때 문제가 됩니다.

예를 들어 [1,1,1]이라는 리스트가 있다면 이 중 어느 1을 기준으로 index를 찾더라도 항상 0번째에 있는 1을 찾아줍니다.

예를 들면 이런 게 반례가 됩니다.

정말 감사해요! 정확하게 짚고 넘어갈 수 있어서 좋았습니다:)