티스토리 뷰
n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.
예를 들어 (-1 5 -3 5 1) 과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.
첫째 줄에 정수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 절댓값이 1,000,000을 넘지 않는 정수가 n개 주어진다.
직관적 아이디어:
- 음수는 그냥 하나만 제거하면 점수가 깎이지만 음수 두 개를 같이 제거하면 플러스가 되므로 음수는 무조건 음수끼리 제거한다. 양수 역시 괜히 음수랑 곱하면 올라갈 점수가 깎여버리므로 양수끼리 제거한다. 즉, 양수는 양수끼리 음수는 음수끼리 제거한다.
- 일반적으로 두 수를 더한 것보다는 곱한 것이 크므로 숫자가 1개 남은게 아닌 이상 계속 2개씩 제거한다.
- 특히, 큰 수끼리 곱할수록 더 결과값이 커지므로 절대값이 큰 수끼리 곱한다.
첫 코드:
arr = []
score = 0
N = int(input());
for i in range(N):
num = int(input());
arr.append(num);
# 양수 * 음수를 할 일은 어차피 없을 것이므로 (점수를 까먹음) 분리하기로 했다.
neg = []
pos = []
for i in arr:
if i > 0:
pos.append(i);
else: # 0은 음수 쪽으로 넣기로 함. 양수 쪽에 넣으면 애꿎은 플러스 점수가 0점이 될 수도 있잖아?
neg.append(i);
while len(pos) > 0:
# pos에서 가장 큰 값 두개 (a, b) 를 빼내서 둘을 곱한다
a = max(pos);
a_ind = pos.index(a);
del pos[a_ind];
if len(pos) == 0: # 원소가 하나밖에 남지 않았을 경우엔 더한다
score += a;
break;
b = max(pos);
b_ind = pos.index(b);
del pos[b_ind];
score += a * b;
while len(neg) > 0:
# 음수인 경우에도 곱하면 어차피 양수가 되므로 똑같다
a = min(neg);
a_ind = neg.index(a);
del neg[a_ind];
if len(neg) == 0:
score += a;
break;
b = min(neg);
b_ind = neg.index(b);
del neg[b_ind];
score += a * b;
print(score);시간 초과가 떴다. 반복문이 두 겹으로 겹치는 것도 아니고 딱히 DP같은걸 쓰는 문제도 아닌 것 같고 수열 길이 제한도 별로 안 큰데 이게 그렇게 오래 걸리나?
아, 조금 생각해보니 굳이 del을 써서 리스트에서 원소를 직접 지운 게 시간을 잡아먹는 것 같다. 전에도 그런 경우가 있었지. 진짜로 지울 필요는 없고 그냥 인덱스를 써서 큰 수부터 보면 시간이 확 줄겠다. 잠깐 큰 수부터? 그럼 정렬을 해야겠네. 정렬을 하면 max() 나 min() 같은걸 쓸 필요도 없겠다.
두번째 코드:
arr = []
score = 0;
N = int(input());
for i in range(N):
num = int(input());
arr.append(num);
neg = []
pos = []
for i in arr:
if i > 0:
pos.append(i);
else:
neg.append(i);
pos.sort(reverse=True);
neg.sort();
for i in range(0, len(pos), 2):
if i+1 == len(pos):
score += pos[i];
else:
score += pos[i] * pos[i+1];
for i in range(0, len(neg), 2):
if i+1 == len(neg):
score += neg[i];
else:
score += neg[i] * neg[i+1];
print(score);pos, neg 리스트를 각각 내림차순 (절대값 기준) 으로 정렬한 뒤 앞에서부터 쭉 보면서 원소를 두 개씩 곱해나간다. 두 개씩 처리하기 위해서 range 함수에 step을 2로 설정해줬다. 마지막에 하나만 남게 되면 그냥 더한다.
아까보다 좀 더 가는 것 같다가 시간 초과도 아니고 '틀렸습니다' 가 떴다.
잉? 로직은 맞는 것 같은데... 큰 것끼리 곱하면 큰 결과가 나오지 않나?
다행히도 반례가 금방 떠올랐다. 위에서 '일반적으로 두 수를 더하는 것보단 곱하는게 크다' 라고 했지만, 그게 아닌 유일한 경우가 있다.
바로 1이랑 다른 양수를 곱하는 경우다.
3 * 1 = 3
3 + 1 = 4
그러니까 리스트를 쭉 보다가 1이 나올 경우엔 두 개를 빼는게 아니라 하나씩 빼는게 1점 더 이득이다.
물론 양수인 경우에만 해당되고 음수 쪽의 -1은 해당되지 않는다. 음수는 음수끼리 곱해야 양수가 되기 때문이다.
0도 다른 양수랑 곱하는 것보다 더하는 게 더 크게 되지만, 0은 하나 남은 음수랑 곱해서 0을 만드는게 더 이득이기 때문에 음수 쪽 리스트에 넣어놨다. 그러므로 추가적인 처리를 해줄 필요가 없다.
그래서 pos 쪽을 도는 for문 안에 한가지 조건을 더 추가해줬다.
마지막 코드:
arr = []
score = 0;
N = int(input());
for i in range(N):
num = int(input());
arr.append(num);
neg = []
pos = []
for i in arr:
if i > 0:
pos.append(i);
else:
neg.append(i);
pos.sort(reverse=True);
neg.sort();
for i in range(0, len(pos), 2):
if i+1 == len(pos):
score += pos[i];
else:
if pos[i] == 1 or pos[i+1] == 1: # 1이 있는 경우 곱하지 않고 각각 더한다
score += pos[i] + pos[i+1];
else:
score += pos[i] * pos[i+1];
for i in range(0, len(neg), 2):
if i+1 == len(neg):
score += neg[i];
else:
score += neg[i] * neg[i+1];
print(score);뭔가 채점이 느릿느릿하길래 불안했지만 맞았다.