우주의 IT 소행성

수열을 묶어 최대의 값을 가져오는 문제 (그리드)

어떤 경우에 최대 값이 나올 수 있는가에 대해 생각 해보자.

입력 된 값들을 오름차순으로 정렬했을 때

앞부분에 [음수, 0, 1]에 해당하는 값이 나온다면 이 값을 우선 계산해주어야 한다.

0번째와 1번째의 값 비교

음수, 음수 -> 곱한다

음수, 0 -> 곱한다

음수, 양수 -> 더한다

이렇게 앞부분의 양수가 아닌 값( 1 제외 )을 없애준 후

나머지는 뒤에서부터(큰 순서로) 2개씩 묶어 곱해주면 된다.

ex) -1 2 1 3일 경우

정렬하면 -1 1 2 3

-1과 2는 (음수, 양수)이기에 더해준다. -> 0

뒤에 2, 3을 묶어 곱해준다 -> 6

0 + 6 -> 6

n = int(input())
data = list(int(input()) for _ in range(n))
data.sort()

result = 0
while True:
    if len(data) == 0:
        break
    elif len(data) == 1:
        result += data.pop(0)
        break
    elif data[0] == 0 and len(data) >= 2:
        result += data.pop(0) + data.pop(0)
    elif data[0] < 0 and len(data) >= 2:
        tmp1 = data.pop(0)
        tmp2 = data.pop(0)
        if tmp2 < 0:
            result += tmp1 * tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 0:
            result += tmp1 + tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 1:
            data.insert(0, tmp2)
            data.insert(0, tmp1)
            tmp1 = data.pop()
            tmp2 = data.pop()
            result += tmp1 * tmp2

    elif len(data) >= 2:
        tmp1 = data.pop()
        tmp2 = data.pop()
        if tmp1 == tmp2 == 1:
            result += tmp1 + tmp2
        elif tmp1 == 1 or tmp2 == 1:
            result += tmp1 + tmp2
        else:
            result += tmp1 * tmp2
print(result)

이 문제를 보자마자, 아 permutation을 써서 나올 수 있는 모든 경우의 수중 30으로 나누어 떨어지는 수의

최대 값이 정답이겠구나! 라는 생각이 들어 코드를 짜보았으나.. 결과는 시간초과였다.

from itertools import permutations
n = input()
data = []

for i in permutations(n, len(n)):
    tmp = int("".join(i))
    if tmp % 30 == 0:
        data.append(tmp)

if data:
    print(max(data))
    exit()

print("-1")

시간 초과가 된 코드는 바로 이것인데, 순열의 경우의 수가 10^5 까지 간다면, 그만큼 시공간 복잡도의 수가 기하급수적으로 늘어나게 됨을 간과하였다.

문제를 다시 곰곰히 살펴보니, 30의 배수가 되는 가장 큰 수 를 만들라는게 제일 큰 힌트였다.

30의 배수 -> 3의 배수 이면서 10의 배수.

결국 최대 값이면서, 맨 오른쪽 끝이 0으로 끝나야하니

입력받은 값을 역순으로 정렬하여 그 값이 30으로 나누어 떨어지기만 하면 되는 것이다.

n = list(input())
n.sort(reverse = True)
n = int("".join(n))
if n % 30 == 0:
    print(n)
else:
    print("-1")

이렇게 쉽게 풀수 있었던 걸 너무 고전하였던 것 같다.

문제를 잘 읽어보는 습관을 들이자.