https://www.acmicpc.net/problem/1744
<문제 풀이>
1. 양수와 음수가 둘 다 나올 수 있기 때문에 따로 생각해야 한다.
<양수>
- 큰 숫자부터 두 개씩 묶어서 곱한 후에 더한다.
<음수>
- 합이 최대가 되려면 되도록 음수가 없어야 한다.
- 음수를 없애기 위해서 음수는 음수끼리 곱해준 뒤에 더하도록 한다.
- 음수 또한 곱했을 때 결과가 가장 커야 하기 때문에 절댓값이 큰 순으로, 즉 작은 숫자부터 두 개씩 묶어서 곱한 후에 더한다.
2. 양수는 내림차순 정렬, 음수는 오름차순 정렬한다.
- 만약 양수던 음수던 숫자가 홀수개 있다면, 마지막 하나의 수는 곱셈을 진행할 수 없다.
- 양수의 경우 가장 작은 양수가 마지막에 남아야 하고, 음수의 경우 가장 큰 음수가 마지막에 남아야 한다.
- 즉 절댓값이 큰 수들부터 곱해야 최대한 큰 수로 만들 수 있기 때문에 다르게 정렬한다.
3. 0과 1을 잘 생각해야 한다.
- 1의 경우 양수이지만, 다른 양수와 곱하면 1이 사라지므로 곱하지 말고 그냥 더해준다.
- 0의 경우 음수도 양수도 아니지만, 음수와 곱하면 음수를 없앨 수 있으므로 음수 쪽에서 계산한다.
Code #1(Python) - while문 사용
import sys
input = sys.stdin.readline
N = int(input())
plus = [] # 양수 저장 리스트
minus = [] # 음수 저장 리스트
result = 0 # 결과값
for _ in range(N):
num = int(input())
if num > 1: # 숫자가 1보다 크면
plus.append(num) # 양수 리스트에 저장
elif num < 1: # 숫자가 1보다 작으면
minus.append(num) # 음수 리스트에 저장
else: # 숫자가 1이면
result += 1 # 그냥 결과값 + 1
plus.sort(reverse=True) # 양수 리스트 큰 순으로 정렬
minus.sort() # 음수 리스트 작은 순으로 정렬
while len(plus) > 1: # 리스트 내 숫자가 2개 이상 남았을 때만 진행
num1 = plus.pop(0) # 리스트 내 제일 큰 양수 추출
num2 = plus.pop(0) # 리스트 내 제일 큰 양수 추출
result += num1 * num2 # 두 수를 곱해서 결과값에 더하기
if plus: # 리스트에 숫자가 남아있다면, 1개만 남아있는 것이므로
result += plus.pop(0) # 그냥 결과값에 더하기
# plus와 메커니즘 동일
while len(minus) > 1:
num1 = minus.pop(0) # 리스트 내 제일 작은 음수 추출(절댓값이 큰 수부터 진행)
num2 = minus.pop(0) # 리스트 내 제일 작은 음수 추출(절댓값이 큰 수부터 진행)
result += num1 * num2
if minus:
result += minus.pop(0)
print(result)
Code #2(Python) - for문 사용
import sys
input = sys.stdin.readline
N = int(input())
plus = []
minus = []
result = 0
for _ in range(N):
num = int(input())
if num > 1:
plus.append(num)
elif num <= 0:
minus.append(num)
else:
result += num
plus.sort(reverse=True)
minus.sort()
for i in range(0, len(plus), 2): # 0번 인덱스부터 2씩 증가하며 반복
if i + 1 < len(plus): # i번 인덱스가 마지막이 아닐 경우(두 개의 숫자를 추출할 수 있는 경우)
result += plus[i] * plus[i + 1] # 두 숫자 곱해서 결과값에 더하기
else: # i번 인덱스가 마지막일 경우,
result += plus[i] # 마지막 숫자만 결과값에 더하기
# plus와 메커니즘 동일
for i in range(0, len(minus), 2):
if i + 1 < len(minus):
result += minus[i] * minus[i + 1]
else:
result += minus[i]
print(result)
Code(Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
public class Boj_1744 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> plus = new ArrayList<>();
ArrayList<Integer> minus = new ArrayList<>();
int result = 0;
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
if (num > 1) {
plus.add(num);
} else if (num < 1) {
minus.add(num);
} else {
result += 1;
}
}
plus.sort(Comparator.reverseOrder()); // 내림차순 정렬
minus.sort(Comparator.naturalOrder()); // 오름차순 정렬
while (plus.size() > 1) {
int num1 = plus.remove(0); // 첫 번째 숫자(제일 큰 숫자) 리스트에서 삭제하고 반환
int num2 = plus.remove(0); // 첫 번째 숫자(제일 큰 숫자) 리스트에서 삭제하고 반환
result += num1 * num2; // 두 수 곱하고, 결과값에 더하기
}
if (plus.size() == 1) { // 아직 리스트에 숫자가 남아있다면,
result += plus.remove(0); // 해당 숫자 결과값에 더하기
}
// plus와 메커니즘 동일
while (minus.size() > 1) {
int num1 = minus.remove(0); // 첫 번째 숫자(제일 작은 숫자) 리스트에서 삭제하고 반환
int num2 = minus.remove(0); // 첫 번째 숫자(제일 작은 숫자) 리스트에서 삭제하고 반환
result += num1 * num2;
}
if (minus.size() == 1) {
result += minus.remove(0); // 첫 번째 숫자(제일 작은 숫자) 리스트에서 삭제하고 반환
}
System.out.println(result);
}
}