백준 1744 두 수 묶기

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

📌 해결순서

문제를 완전히 이해하는데도 시간이 많이 걸렸고, 두 수를 묶는걸 어떻게 코드로 구현을 해야 하는지에 대해 정말 많은 시간을 써가면서 고민했다.. :(

 

아래 표는 , 두 수를 묶는 경우에 어떤 수식을 사이에 넣어야지 더 커지는지에 대해 정리한 표이다

숫자	숫자	수식
양수(>1)	양수(>1)	*
음수(<=1)	음수(<=1)	*
양수(>1)	1	+
음수(<=1)	1	+
양수(>1)	0	+
음수(<=1)	0	*

 

1. 입력으로 주어지는 수열에 대해, 양수 , 음수 + 0 , 1 로만 이루어진 3가지 배열을 따로 만든다

2. 양수로만 이루어진 배열은 내림차순 , 음수 + 0 으로만 이루어진 배열은 오름차순 정렬한다.

ex)

arr_pos = [3 , 2 , 4] 인 경우,  (4 * 3) + 2 = 14 로 가장 크게 만들수 있다

arr_neg = [-5, -7, -3, 0] 인 경우 , (-7 * -5) + (-3 * 0)  = 35 로 가장 크게 만들수 있다

3. 배열의 길이가 짝수인 경우는 처음숫자부터 2개씩 묶어서 차례로 더하고, 홀수인 경우 마지막 숫자를 제외하고 2개씩 묶어서 더한후 마지막 숫자를 더해준다

4. 1은 앞의 수가 음수 , 양수 상관없이 항상 더하는게 수를 크게 만들수 있으므로 모든 연산이 끝난후, 수열에 있는 1의 갯수만큼 더해준다

📌 코드

import sys
input = sys.stdin.readline

n = int(input())
lst = [int(input()) for _ in range(n)]

arr_one = []
arr_pos = []
arr_neg = []

for num in lst:
    if num <= 0:
        arr_neg.append(num)
    elif num == 1:
        arr_one.append(num)
    else:
        arr_pos.append(num)

arr_neg.sort()
arr_pos.sort(reverse=True)

res = 0

if len(arr_pos) % 2 == 0:
    for i in range(0, len(arr_pos), 2):
        res += arr_pos[i] * arr_pos[i + 1]
else:
    for i in range(0, len(arr_pos) - 1, 2):
        res += arr_pos[i] * arr_pos[i + 1]
    res += arr_pos[len(arr_pos) - 1]

if len(arr_neg) % 2 == 0:
    for i in range(0, len(arr_neg), 2):
        res += arr_neg[i] * arr_neg[i + 1]
else:
    for i in range(0, len(arr_neg) - 1, 2):
        res += arr_neg[i] * arr_neg[i + 1]
    res += arr_neg[len(arr_neg) - 1]

for num in arr_one:
    res += num


print(res)