백준 1744번 - 수 묶기

출처 : 1744번: 수 묶기 (acmicpc.net)

1744번: 수 묶기

---

수 묶기 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

128 MB

14371

3931

3176

26.863%

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5} 일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한 번만 묶거나, 아니면 묶지 않아야 한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작은 자연수이다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

 

---

[ 문제 해설 ]

 

 

이 문제는 수열의 합을 구할 때, 두 수를 곱하는 기법을 이용하여 최대를 구하는 문제인데.

 

이런 문제는 어떻게 해야 최대가 나올까를 생각하면서 차근차근 따져가면서 풀어보면 그런 상황의 조건이 하나하나씩 나오게 되고, 그런 상황을 고려하여 코딩해주면 됩니다.

 

그림으로 해설하겠습니다.

 

그림 1 - 수 묶기 아이디어

3) 조건에서 음수가 짝수면이라는 뜻입니다.

 

그림 2 - 수 묶기 아이디어

이러 식으로 코딩을 해가고 반례가 나오면 수정을 하는 형태로 코딩했습니다.

 

---

[ 코드 ]

 

위 그림의 상황에 따라 코딩했습니다. 

 

n = int(input())

sequence = []
negative = []
positive = []
res = 0
for i in range(n):
    i = int(input())
    sequence.append(i)

for k in sequence:
    if k < 0:
        negative.append(k)
    elif k > 0:
        positive.append(k)
    else:
        negative.append(k)

negative.sort()
positive.sort(reverse=True)
# print(negative)
u = len(negative)
if 0 in negative:
    if u % 2 == 0:
        for q in range(0, u, 2):
            res += negative[q] * negative[q + 1]
    else:
        for w in range(0, u - 1, 2):
            res += negative[w] * negative[w + 1]
else:
    if u % 2 == 0:
        for q in range(0, u, 2):
            res += negative[q] * negative[q + 1]
    elif u % 2 != 0 and u != 1:
        for w in range(0, u - 1, 2):
            res += negative[w] * negative[w + 1]
        res += negative[u - 1]
    else:
        res += negative[0]
# print("음수합:", res)
# print(positive)
v = len(positive)
if 1 in positive:
    x = positive.count(1)
    # print(x)
    if v - 1 > x:
        if v % 2 == 0:
            for s in range(0, v - x, 2):
                res += positive[s] * positive[s + 1]
            res += x
        else:
            for t in range(0, v - x, 2):
                res += positive[t] * positive[t + 1]
            res += x
    else:
        for h in positive:
            res += h
else:
    if v % 2 == 0:
        for r in range(0, v, 2):
            res += positive[r] * positive[r + 1]

    else:
        for f in range(0, v - 1, 2):
            res += positive[f] * positive[f + 1]
        res += positive[v - 1]

print(res)

 

---

후기

 

상황을 고려하여 코딩하는 문제로 쉽지 않았지만

발견된 반례인 상황도 많아서

풀 수 있었습니다.