[Python] 백준(BOJ): 1744 수 묶기

문제

1744번: 수 묶기

---

풀이

수를 묶는 규칙을 모두 고려해야 하는 greedy 문제이다

 

a. 반례

처음에는 음수/양수/0에 대한 경우를 나누지 않고,
단순 오름차순 정렬 후 구간별로 최대합(_add) or 최대곱(_mul)을 구하여 더해주는 방향으로 접근하였으나

일부 테스트 케이스에 대해 실패하였다..
반례를 찾아보니, 이 소스코드는 0 또는 음수에 대한 합/곱의 예외를 고려하지 못한다는 것을 발견했다

5
4
-1
0
1
2 

 

작성했던 소스코드는 다음과 같다

n = int(input())
data = [int(input()) for i in range(n)]
data.sort()

answer = 0
while data:
    add = [data[i] + data[i + 1] for i in range(len(data) - 1)]
    add.append(data[len(data) - 1])
    _add = max(add)

    mul = [data[i] * data[i + 1] for i in range(len(data) - 1)]
    mul.append(data[len(data) - 1])
    _mul = max(mul)

    if _add < _mul:
        idx = mul.index(_mul)
        answer += _mul
    else:
        idx = add.index(_add)
        answer += _add

    if idx < len(data)-1:
        data.remove(data[idx + 1])
    data.remove(data[idx])

print(answer)

 

b. 최종 풀이

양수/음수/0으로 나누어서 모든 경우의 수를 고려해보니, 최대값을 구해낼 수 있는 규칙은 다음과 같았다

양수, 양수	곱셈
음수, 음수	곱셈
0, 음수	곱셈	-부호를 없애서 0으로 만들어버림 (음수<0)
양수, 음수	덧셈
0, 양수	덧셈
1, 양수	덧셈	1의 경우 최대값을 구하기 위해서는 곱이 아닌 합을 수행해야 함
1, 음수	덧셈

 

따라서 양수, 음수, 0을 저장할 list를 별도로 분리하고

• 양수의 경우에는 _pos에 내림차순으로 정렬한 뒤, 2개씩 곱셈 수행 (홀수 개인 경우, 가장 작은 수는 더해줌)
• 음수와 0을 _neg에 오름차순으로 정렬한 뒤, 2개씩 곱셈 수행 (홀수 개인 경우, 마지막 수는 더해줌)
• 1의 경우에는 _one에 별도로 저장한 뒤, 전부 더해줌

n = int(input())
_pos = []
_neg = []
_one = []

for _ in range(n):
    num = int(input())
    if num <= 0:
        _neg.append(num)
    elif num > 1:
        _pos.append(num)
    else:
        _one.append(num)

_pos.sort(reverse=True)
_neg.sort()

answer = 0
for i in range(0, len(_pos) - 1, 2):
    answer += (_pos[i] * _pos[i + 1])
if len(_pos) % 2 != 0:
    answer += _pos[len(_pos) - 1]

for i in range(0, len(_neg) - 1, 2):
    answer += (_neg[i] * _neg[i + 1])
if len(_neg) % 2 != 0:
    answer += _neg[len(_neg) - 1]

answer += len(_one)
print(answer)