soph456   4년 전

들어오는 수에서 음수와 양수를 분리해서 저장합니다. 단 0과 1은 따로 저장합니다.

양수는 큰 수(9*8) 끼리 곱하고 음수는 작은 수(-9 * -8)끼리 곱하는게 목적입니다.

그런데 곱하려면 양수와 음수의 수가 각각 짝수가 되어야 합니다

중간에 if는 각 양수와 음수의 갯수가 짝수가 아닐때의 예외처리입니다.

1. 음수1개,  수열에 0이 없음 => 그냥 합에 음수를 더하고 해당 음수를 이미 더했으니 배열에서 제거

2. 음수가 홀수개, 수열에 0이 없음 => 제일 작은 음수를 합에 더하고 해당 배열에서 제거(이미 계산 완료되었으므로)

3. 음수가 홀수개, 수열에 0이 있음 =>  제일 작은 음수를 0과 곱하면 0일테니 그냥 해당 배열에서 제거 

4. 양수가 홀수 개=> 제일 작은 양수를 합에 더하고 해당 배열에서 제거


각 과정을 거친후에 2개씩 짝지어 곱하여서 더합니다

이때, 따로 빼둔 1도 마지막에 저장하고, 합을 출력합니다.

이상 알고리즘 설명을 구현한 내용인데 '틀렸습니다'가 나와서 어느부분에서 반례인지 모르겠습니다.

가장 작은 경우나 가장 큰경우 또한 해보았습니다. 가장 큰 경우는 2의 31승을 넘어가지않으니 int문제는 아닌 것 같습니다만 제가 어떤 반례를 놓쳤는지 알려주시면 감사하겠습니다.

nablekim94   3년 전

반례

N : 6

데이터 : 50 3 -1 20 2 10

결과 : 129

답 : 1031

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