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

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은 10,000보다 작은 자연수이다.

둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다.

수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

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

예제 입력 1

4
-1
2
1
3

예제 출력 1

6

---

설명

해당 문제는 그리디 문제다.

수열이 주어졌을 때 이를 (양수), (0, 음수) 나눠 입력을 받습니다.

 

양수의 경우

내림차순으로 정렬합니다.

해당 인덱스 값 * 다음 인덱스 값 (?) 해당 인덱스 값

0인 덱스부터 살피며 현재 인덱스와 다음 인덱스의 곱이 더 큰 경우는 곱을 결과에 더해주고 인덱스는 2 증가합니다.

같거나 작은 경우에는 해당 인덱스 자체가 더 큰 경우는 해당 인덱스만 결과에 더하고 인덱스는 1 증가합니다.

만약 1, 1이라면 두 값의 곱은 1이고 해당 인덱스는 1이기 때문에 해당 경우는 해당 인덱스인 1만을 결과에 더하게 됩니다.

(음수, 0)의 경우

오름차순으로 정렬합니다.

음수의 경우 값이 작을수록 곱했을 때 큰 값이 나오게 됩니다.

예를 들어 -1 -5 -6이 있다면

오름차순이면 -6 -5 -1로 먼저 -6과 -5를 곱해서 30이 나오고 -1을 더했을 때 결과가 더 큰 결과가 나옵니다.

내림차순이면 -1 -5 -6으로 -1*-5를 곱해서 5가 나오고 -6을 더했을 때 -1이라는 결과로 이전 오름차순보다 값이 작아진 것을 확인할 수 있습니다.

 

다음 연산부터는 양수와 마찬가지로

0인 덱스부터 살피며 현재 인덱스와 다음 인덱스의 곱이 더 큰 경우는 곱을 결과에 더해주고

해당 인덱스 자체가 더 큰 경우는 해당 인덱스만 결과에 더해주게 됩니다.

코드