Baekjoon #1744 - 수 묶기

목차

1. 문제

2. 입출력 예시

3. 문제 풀이

1. 문제

• 백준알고리즘 문제 - 1744번 수 묶기

2. 입출력 예시

입력 예시	출력 예시
4 -1 2 1 3	6

3. 문제 풀이

이 문제는 코드를 총 3번 제출하여 통과하였는데, 그 이유는 테스트케이스 선정에 오류가 있었기 때문이었다. 따라서, 이 문제를 해결할 때에는 테스트케이스를 잘 선정하여 예외사항을 처리하여야 한다. 최종 제출할 때 선정한 테스트케이스는 아래와 같다.

• 수열의 개수(N) : 11
• 수열 : [9, 8, 7, 6, 5, 4, 3, 2, 0, -10, -20]

실패하였을 때는 수열을 오름차순으로 정렬 후 x번째의 수와 x+1번째의 수를 더한 값과 이 둘을 곱한 값 중 큰 값을 최종 값에 더하는 경우만 적용하였다. 그러나, 이와 같이 한 개의 분기만 적용할 경우 음수 × 음수 = 양수라는 사실이 누락된다. 따라서, 최종 제출 시에는 수열의 수를 양수, 음수 또는 0으로 나눈 후 기존의 연산을 수행하였다.

서로 다른 두 수를 묶을 떄 결과 값을 최대로 하기 위해서는 아래의 조건을 모두 만족해야 한다.

• 양수인 경우, number1 × number2 > number1 + number2
• 음수인 경우, number1 × number2
• 음수와 0인 경우, number × 0

따라서, 양수인 경우에는 리스트의 인덱스를 사용하여 요소를 호출할 때 내림차순, 리스트의 요소를 추출할 때 오름차순으로 정렬하여야 하며, 0 또는 음수인 경우에는 인덱스를 사용하여 요소를 호출할 때 오름차순, 리스트의 요소를 추출할 때 내림차순으로 정렬하여야 한다. 이와 같은 조건을 적용하여 프로그램의 동작 순서를 나타내면 아래와 같다.

• 수열의 개수(N)를 입력받는다.
• 수열의 개수만큼 반복하며 수열에 포함할 수를 입력받아 리스트(numbers)에 추가한다.
• 양수인 경우의 리스트(plus)와 0 또는 음수인 경우의 리스트(minus)를 빈 리스트로 초기화한 후 while문을 통해 수열의 개수만큼 반복한다. 반복할 때마다 수열의 수를 빼내어(pop) 양수, 0 또는 음수로 구분하여 각각의 리스트에 나누어주고, 수열의 개수를 1 감소시킨다.
• 양수가 담긴 리스트는 오름차순으로, 음수가 담긴 리스트는 내림차순으로 정렬한다.
• 결과 값(total)을 0으로, 양수의 개수를 양수 수열의 길이로, 0 또는 음수의 길이를 음수 수열의 길이로 초기화한다.
• while문을 통해 양수의 개수가 1보다 클 때까지만 반복한다. 반복하는 동안 리스트에서 2개의 요소를 추출(pop) 후 이 둘을 합한 값과 곱한 값을 비교하여 더 큰 값을 결과 값에 더한다. 반복마다 2개의 요소를 추출하였으므로 양수의 개수에 2를 뺀다.
• 반복이 종료되면 양수의 개수를 확인한다. 만약 양수의 개수가 0이 아닐 경우(즉, 1개일 경우) 리스트에서 나머지 요소를 추출 후 결과 값에 더한다.
• while문을 통해 음수의 개수가 1보다 클 때까지만 반복한다. 반복하는 동안 리스트에서 2개의 요소를 추출(pop) 후 이 둘을 합한 값과 곱한 값을 비교하여 더 큰 값을 결과 값에 더한다. 반복마다 2개의 요소를 추출하였으므로 음수의 개수에 2를 뺀다.
• 반복이 종료되면 음수의 개수를 확인한다. 만약 음수의 개수가 0이 아닐 경우(즉, 1개일 경우) 리스트에서 나머지 요소를 추출 후 결과 값에 더한다.
• 결과 값을 출력 후 프로그램을 종료한다.

이를 코드로 나타내면 아래와 같으며, 메모리는 28,776 KB, 시간은 64 ms가 소요되었다.

N = int(input())

numbers = sorted([int(input()) for _ in range(N)])

plus = []
minus = []

while N > 0:
    tmp = numbers.pop()
    if tmp > 0:
        plus.append(tmp)
    else:
        minus.append(tmp)
    N -= 1


plus = sorted(plus)
minus = sorted(minus, key=lambda x: -x)

total = 0

P = len(plus)
M = len(minus)

while P > 1:
    tmp1 = plus.pop()
    tmp2 = plus.pop()
    if tmp1 * tmp2 > tmp1 + tmp2:
        total += tmp1 * tmp2
    else:
        total += tmp1 + tmp2
    P -= 2

if P:
    total += plus.pop()

while M > 1:
    tmp1 = minus.pop()
    tmp2 = minus.pop()
    if tmp1 * tmp2 > tmp1 + tmp2:
        total += tmp1 * tmp2
    else:
        total += tmp1 + tmp2
    M -= 2

if M:
    total += minus.pop()

print(total)