백준 1744번
https://www.acmicpc.net/problem/1744
문제설명
N개의 숫자를 입력받아 수열을 묶어 최대값을 구하는 문제 (묶인 값들은 서로 곱해진다.)
ex) input = 1 2 3 4
1+2+(3*4) = 15
접근
1. 음수가 짝수개이면 서로 곱해 양수가 나오므로 최대값이 된다.
2. 양수는 1을 제외한 값들을 큰 수부터 차례대로 곱하면 최대값이 된다.
3. 1은 다른 양수와 곱하는 것보다 따로 더해주는게 더 큰값이 나옴
4. 0이 존재하고 음수가 홀수개이면 음수를 하나 없앨수 있다.
코드
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
priority_queue<int,vector<int>,greater<int>> pq1; //음수
priority_queue<int> pq2; //양수
int N;
cin >> N;
long long sum = 0;
int zero=0;
int one = 0;
int tmp;
for (int i = 0; i < N; i++)
{
cin >> tmp;
if (tmp == 0)
zero++;
else if (tmp == 1)
one++;
else if (tmp < 0)
pq1.push(tmp);
else
pq2.push(tmp);
}
if (pq1.size() % 2 == 1 && zero != 0) //음수가 홀수 갯수이면서 입력받은 값중 0 이있으면 0삽입 ( 음수 * 0 = 0 으로 최대값)
pq1.push(0);
else if(pq1.size() % 2 ==1 && zero ==0) //음수가 홀수 갯수이면서 0이 없으면 1추가 (음수 * 1 = 결과값 같음 2개씩 묶어주기위해서 추가)
pq1.push(1);
if (pq2.size() % 2 == 1) //양수의 갯수가 홀수이면 1추가 결과값 같음
pq2.push(1);
while (!pq2.empty())
{
int num1 = pq2.top();
pq2.pop();
int num2 = pq2.top();
pq2.pop();
sum += (num1 * num2);
}
while (!pq1.empty())
{
int num1 = pq1.top();
pq1.pop();
int num2 = pq1.top();
pq1.pop();
sum += (num1 * num2);
}
sum += one;
cout << sum;
return 0;
}
코드설명
1. 우선수위큐를 두개 생성한다(음수,양수)
2. 음수는 오름차순 정렬, 양수는 내림차순 정렬
ex) -5 -4 -1 5 4 1
3. 0과 1의 개수는 따로 세어준다
4. 음수 갯수가 홀수이면서 0이 존재하면 0을 큐에 추가 그렇지 않으면 1을추가
(0을 곱하면 0이되어 사라지고 1을곱하면 결과값은 그대로 쌍을 이루어주기 위해 추가)
5. 양수 갯수 홀수 이면 1을추가
'알고리즘 > 백준 Baekjoon' 카테고리의 다른 글
백준 2309번 일곱 난쟁이(JAVA) (0) | 2023.01.16 |
---|---|
백준 9093번 단어 뒤집기(JAVA) (0) | 2022.12.27 |
백준 9095번 1,2,3 더하기 (C++) (0) | 2021.06.02 |
백준 20365번 블로그2 (C++) (0) | 2021.04.23 |
백준 2812번 - 크게만들기 (C++,deque) (0) | 2021.04.21 |