[BOJ #1744 / Python] 수 묶기

이건·2023년 8월 24일

baekjoon greedy

Algorithm

목록 보기

2/2

백준 solved.ac 기준 골드4에 배치된 문제이다.

문제링크:
https://www.acmicpc.net/problem/1744

문제 분석

문제를 살펴보자.

문제를 간단히 요약하자면 수열이 주어졌을 때 수열에서 인접한 두 수를 한 번만 묶을 수 있다.

이렇게 묶인 두 수는 곱할 수 있다.

문제에서 요구하는 정답은 수열의 합이 최대가 나오게 묶었을 때 그 합이다.

또한 수열의 수는 음수까지도 나올 수 있다.

이 조건을 잊으면 안된다.

해결 아이디어

이 문제를 보는 순간 곱셈에 대해서 떠올린 사람이 많을 것이다.

조건을 생각해보면

0과 1을 제외한 양수에서 두 수는 곱한 것이 더한 것보다 크다.

음수끼리는 곱한 것이 더 크고, 음수와 0을 곱하면 더한 것이 크다.

하지만 음수와 양수를 곱하는 것은 더하는 것보다 작다.

이러한 상황에서 생각해보면 어느정도 답이 나온다.

최대한 곱할 수 있는 것들은 곱하고 나머지는 더하기만 하면 된다.

따라서 그리디 알고리즘이라고 할 수 있다.

구현은 코드를 살펴보며 얘기하자.

구현이 조금 까다로웠다..

Code (python)

import sys

read = sys.stdin.readline

n = int(read())
seq = [int(read()) for _ in range(n)]
seq.sort()
cind = 0 if seq[-1] > 0 else n
for i in range(n - 1):
    if seq[i] <= 0 < seq[i + 1]:
        cind = i + 1
tmp = []
righti = n - 1
while cind <= righti:
    if righti - 1 >= cind and (seq[righti] * seq[righti - 1]) > (seq[righti] + seq[righti - 1]):
        tmp.append(seq[righti] * seq[righti - 1])
        righti -= 2
    else:
        tmp.append(seq[righti])
        righti -= 1

lefti = 0
while lefti < cind:
    if lefti + 1 < cind and (seq[lefti] * seq[lefti + 1]) > (seq[lefti] + seq[lefti + 1]):
        tmp.append(seq[lefti] * seq[lefti + 1])
        lefti += 2
    else:
        tmp.append(seq[lefti])
        lefti += 1
print(sum(tmp))

앞에 아이디어에서 말했듯이 조건이 상당히 많은 문제이다.

사실 길이가 홀수인지 짝수인지에 대해서도 구분을 하는 사람들도 많은데 고민하다가 알아냈다.

우선 수열을 이루는 수는 -1,000 <= n <= 1,000 이다.

우리가 조심해야 할 것은 수열에서 1은 다른 수와 묶지 않고 더하고

0은 음수하고만 묶을 수 있고

양수와 양수는 묶고 음수와 양수는 묶지 않고 음수와 음수는 묶어야 한다.
(조건이 많다...)

이러한 조건들은 수열을 양수 수열과 음수 수열 부분으로 나누면 깔끔하게 해결된다.

cind = 0 if seq[-1] > 0 else n
for i in range(n - 1):
    if seq[i] <= 0 < seq[i + 1]:
        cind = i + 1

이 부분에서 양수와 음수를 나누는 인덱스를 찾는다.

그런데 위에서 있던 조건 중 음수는 0과 곱하면 더 큰 수가 된다.

따라서 음수 부분에 0도 포함을 한다.

그리고 만약 수열의 마지막 원소가 양수이면 구분하는 인덱스가 0부터 시작해도 되는데 만약 마지막 원소가 음수이면 수열 전체가 음수라는 소리이므로 양수 부분을 계산하면 안된다.

따라서 이 때는 나누는 인덱스에 n을 넣는다.

tmp = []
righti = n - 1
while cind <= righti:
    if righti - 1 >= cind and (seq[righti] * seq[righti - 1]) > (seq[righti] + seq[righti - 1]):
        tmp.append(seq[righti] * seq[righti - 1])
        righti -= 2
    else:
        tmp.append(seq[righti])
        righti -= 1

lefti = 0
while lefti < cind:
    if lefti + 1 < cind and (seq[lefti] * seq[lefti + 1]) > (seq[lefti] + seq[lefti + 1]):
        tmp.append(seq[lefti] * seq[lefti + 1])
        lefti += 2
    else:
        tmp.append(seq[lefti])
        lefti += 1