Backjoon_그리디_1744_수 묶기
직관적으로 상당히 쉬운 문제라 생각했는데 3번이나 틀렸다.
음수는 작은 값부터 정렬시키고(절댓값이 크기 때문에)
양수는 큰 값부터 정렬시킨다.
그리고 양수의 갯수=n,이고 음수의 갯수=m 이라 했을 때
n이 짝수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n이 홀수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]
m이 짝수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-2] x v[n-1]
n이 홀수라면)
sum += V[0] x V[1] + V[2] x v[3] + · · · + v[n-3] x v[n-2] + v[n-1]
여기서 1차 오류가 생겼다.
m이 홀수일 때 가장 작은 절댓값을 가진 v[n-1]은 음수기 때문에 더하면 손해이다.
만약 기존 수열에 0이 존재할 경우 음수를 더해주지 않아도 되므로
0이 있는지를 체크해야한다.
2차 오류는 고민해봐도 생각해낼 수가 없어서 인터넷에서 찾아봤다.
만약 1 1 1 1 이 입력될 경우
(1x1) + (1x1) 보다 1 + 1 + 1 + 1 이 더 크므로
1은 양수 수열을 골라낼 때 선택하지 않고 갯수만 체크해주고 마지막에 한번에 더해주기로 했다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { return a > b; }
bool cmp1(int a, int b) { return a < b; }
int main()
{
int n;
int sum = 0;
int zero_flag = 0;
int one_cnt = 0;
vector<int> seq;
vector<int> seq_pos;
vector<int> seq_neg;
cin >> n;
while (n--)
{
int s;
cin >> s;
seq.push_back(s);
}
sort(seq.begin(), seq.end(),cmp);
for (int i = 0; i < seq.size(); i++)
{
if (seq[i] > 1) seq_pos.push_back(seq[i]);
else if (seq[i] < 0) seq_neg.push_back(seq[i]);
else if (seq[i] == 0) zero_flag = 1; // 1차오류
else if (seq[i] == 1) one_cnt++; // 2차오류
}
sort(seq_neg.begin(), seq_neg.end(), cmp1);
if (seq_pos.size() % 2 == 0)
{
for (long unsigned int i = 0; i < seq_pos.size(); i = i + 2)
{
sum += (seq_pos[i] * seq_pos[i + 1]);
}
}
else
{
for (long unsigned int i = 0; i < seq_pos.size()-1; i = i + 2)
{
sum += (seq_pos[i] * seq_pos[i + 1]);
}
sum += seq_pos[seq_pos.size() - 1];
}
if (seq_neg.size() % 2 == 0)
{
for (long unsigned int i = 0; i < seq_neg.size(); i = i + 2)
{
sum += (seq_neg[i] * seq_neg[i + 1]);
}
}
else
{
for (long unsigned int i = 0; i < seq_neg.size() - 1; i = i + 2)
{
sum += (seq_neg[i] * seq_neg[i + 1]);
}
if (!zero_flag) { // 0이 없다면
sum += seq_neg[seq_neg.size() - 1];
}
}
cout << sum+one_cnt;
return 0;
}
Author And Source
이 문제에 관하여(Backjoon_그리디_1744_수 묶기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soonyubi/Backjoon그리디1744수-묶기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)