[백준]1744번 수 묶기 - C++

https://www.acmicpc.net/problem/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은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

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

---

 

양수 기준 큰 수를 여러 번 더해야 더 했을 때 큰 수가 나온다. 따라서 양수 라면 큰 순서 대로 두 수를 곱해주면 된다.

음수의 경우 역시 작은 수 (절댓값이 큰 수) 두 개를 곱해서 더해야 합이 최대가 된다.

그리고 0 이 있으면서 음수가 홀수인 경우 가장 작은 음수를 0과 곱해 더하지 않을 수 있다.

따라서 양수와 음수를 각각의 우선순위큐에 삽입하여 두 개씩 곱해 나간다.

-> 양수의 경우

   - 짝수일 경우 모두 곱해서 더하면 되고

   - 홀수 일 경우 마지막 수 (가장 작은 수)만 곱하지 않고 더하면 된다.

-> 음수의 경우

    - 짝수일 경우 모두 곱해서 더하면 되고

    - 홀수 일 경우

        - 0이 존재한다면 마지막 수(절대 값이 가장 작은 수)는 더하지 않는다.

        - 0이 존재하지 않는다면 마지막 수를 합에 더한다.

---

 처음 코드를 작성하고 예제를 하기 전 다 풀었다고 생각했다. 가장 큰 수 두 개를 곱하는 방법이었다. 하지만 예제를 해보니 0이 있을 때를 미처 생각하지 못했다. 그래서 가장 절댓값이 큰 음수를 0과 곱하면 되겠다고 생각하고 코드를 변경하고 제출하였더니 틀렸다고 나왔다. 다시 생각해 보니 음수 두 개를 곱하면 양수가 되는데 무턱대고 절댓값이 큰 음수를 없애버렸던 것이다. 그래서 양수와 음수의 우선순위 큐를 두고 다시 작성하였는데 틀렸다고 나왔다. 양수의 경우 1은 곱하는 것보다 더하는 것이 이득인 것을 첫 작성 때는 생각했는데 코드를 바꾸면서 사라졌던 것이다. 해당 부분을 추가하니 정답을 받을 수 있었다.

 문제를 보자마자 우선순위 큐를 생각해 냈다. 처음에는 양 옆으로만 곱할 수 있는 줄 알아서 pair <값, 인덱스>로 둘 생각이었으나 자리를 바꿀 수 있었다. 문제를 대충 보고 무턱대고 풀었으면 시간을 버릴 뻔했다. 그다음에도 첫 제출을 신중히 하겠다고 생각을 했지만 쉬운 것 같아 빨리 풀겠다는 생각에 더 생각을 안 하고 제출해 버렸다. 코테에서 이런 문제를 틀렸을 생각 하니 아찔하다!