백준 1744. 수 묶기

tose33 2022. 11. 29. 13:14

1744번: 수 묶기

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에

www.acmicpc.net

두 수끼리 묶어 곱하고, 그 수들의 합이 최대가 되게 해야 한다.

수는 다음과 같이 나눌수 있다.

음수, 0, 1, 2 이상의 양수

우선 2 이상의 양수 끼리는 큰 값끼리 곱해야 큰 값이 나오기 때문에 정렬 후에 두 개씩 묶으면 된다.

1은 음수랑 곱하면 음수가 되고, 0이랑 곱하면 0, 2이상의 양수와 곱하면 그 양수가 되버리기 때문에 어떠한 값과도 묶으면 안된다.

0은 음수랑 곱해주면 음수값이 0이 되기 때문에 음수랑 묶는다.

음수끼리는 2이상의 양수와 마찬가지로 정렬후 두 개씩 묶으면 된다.