[백준/1744/파이썬] 수 묶기

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

1744번: 수 묶기

Problem

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

조건

• 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다.
• 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다.
• 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
• 수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
• 첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

SOL

Binding을 하는 개념이다. 근데, binding을 할 때, 위치에 상관없이 가능하고, 한번 묶은 수는 다른 수와 묶을 수 없다.

 

완전탐색

묶을 수를 2개 뽑는 모든 경우 :nC2

하지만, 1개가 binding된 상태에서, 나머지를 다 더해줄지, 나머지에서 또 nC2를 해서, 2개를 뽑은 뒤 또 바인딩을 해줄지, 모르는거다. 완전탐색은 이 같은 경우를 다 봐야하기 때문에,

nC2 *n-2C2* n-4C2 ;...이므로ㅡ (N^2)*50 = N^100 이라는 엄청난 수가 나온다.

완전탐색으로는 불가능한 문제다.

DP 

재귀적인 관계가 성립하지만, Subproblem을 가지고 답을 구하기가 어렵다.

만약, 두 수가 연속적으로 묶인다고 하면, p~q까지 Dp table을 세우겠지만,  묶이는것도 연속적이지 않고, 1번만 묶는게 가능하다.

Greedy

숫자를 곱하고, 더하는 과정에 대해서 생각해보자.

숫자는 음수,양수,0 3가지 종류가 있다. 그리고, 곱하는 과정이 있으니까, 1은 곱하는것보단, 더 하는게 더 크게 만들 수 있음.

• 음수 : 제일 작은 음수 *2번째로 작은 음수= 제일 큰 수 (정렬이 필요하다) 
• 양수 : 제일 큰 수*두번째로 큰수 = 제일 큰 수 (정렬이 필요하다) 
• 0은 음수와 곱해도 0이고, 양수와 곱해도 0이다.따라서, 0은 음수의 배열에 넣고, 짝지을 수있으면 짝 지어주고,아니면 그냥 더 해준다. (짝 지을 수 있는 조건, 길이가 짝수냐 홀수냐 판단!)
• 양수 1은 곱하는 것보단, 더 하는게 좋다. (One List 생성)

왼쪽은 내가 생각한 조건이고, 오른쪽은 어떻게 구현할지 구현 방법을 괄호안에 적어놓았다.

코드로 구현하면서, 하나씩 적용해보자. 

# Greedy
N =int(input())
pList=[]
nList=[]
oneList=[]

for _ in range(N):
    num = int(input())
    if num>1:
        pList.append(num)
    elif num<=0:
        nList.append(num)
    else:
        oneList.append(num)
#sorting
#sorting함으로써, 선형적으로 반복이 가능해짐.
#postivie = descending sort, negative = ascending sort
#if postive ={7,63,34,3} => {63,34,7,3} 이렇게 해야, 앞에서 2개씩 묶어서 곱하면 최대가 됨.
pList.sort(reverse=True)
nList.sort()

ans=0
# Positive 
if len(pList)%2==0:
    for i in range(0,len(pList),2):
        ans += pList[i]*pList[i+1]
else:
    for i in range(0,len(pList)-1,2):
        ans += pList[i]*pList[i+1]
    ans += pList[len(pList)-1] 
# Negatvie
if len(nList)%2==0:
    for i in range(0,len(nList),2):
        ans+=nList[i]*nList[i+1]
else:
    for i in range(0,len(nList)-1,2):
        ans+=nList[i]*nList[i+1]
    ans+= nList[len(nList)-1]

ans+=sum(oneList)

print(ans)