문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
1744번: 수 묶기 문제보기
문제
길이가 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은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 $$2^31$$보다 작다.
예제 입력 1
4
-1
2
1
3
예제 출력 1
6
예제 입력 2
6
0
1
2
4
3
5
예제 출력 2
27
최적의 해를 구하는 그리디 문제이다.
이 문제는 양수와 음수, 0과 1을 생각해 주어야한다.
양수의 경우: 가장 큰 수를 기준으로 정렬하여 곱했을 때, 큰 값이 나온다.
음수의 경우: 가장 작은 수를 기준으로 정렬하여 곱했을 때, 큰 값이 나온다. (-5, ..., -2, -1,) (음수 * 음수는 양수이기 때문에)
1의 경우 무조건 더해주는 것이 수를 크게 만든다. (1*N<N+1 이기 때문)
0의 경우는 음수들을 다 묶고(음수끼리 곱하고) 남은 것이 있을 때 그 값을 더하게 되면 결과값이 작아지므로 마지막으로 남은 음수값을 0과 곱한다.
남은 음수값과 0을 곱하기 위해선 0을 음수 데이터 배열에 넣어주면 된다.
가장 끝에 배치되므로 0이 남으면 더해지고 남는 음수값이 생기면 자동으로 곱해진다.
정답
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(input())
plus=[] # 양수 데이터 리스트
minus=[] # 음수 데이터 리스트
res=0
for i in range(N):
num=int(input())
if num>1: # 1보다 큰 양수인 경우
plus.append(num)
elif num<=0: # 0과 음수인 경우
minus.append(num)
else: # 1인 경우는
res+=1 # 그냥 더하는게 가장 best
plus.sort(reverse=True) # 큰 수 끼리 묶기 위해
minus.sort() # 작은 수 끼리 묶기 위해
for i in range(0,len(plus),2): # [a,b], [plus[i],plus[i+1]] 이런식으로 2개씩 보기 위해
if i+1<len(plus): # plus 리스트 안 범위에서
res += (plus[i]*plus[i+1]) # 양수끼리 곱해줌
else: # i+1이 plus 리스트 범위 밖이면. 즉, i+1은 없는 경우, 즉, 짝이 없는 경우
res += plus[i] # 짝없이 홀로 있는 나머지를 더해줌
for i in range(0,len(minus),2): # 2개씩 가져옴
if i+1<len(minus): # minus 리스트 안 범위에서
res += (minus[i]*minus[i+1])
else:
res += minus[i]
print(res)
