우노
[Greedy] 백준 1744번 "수 묶기" C++ 풀이 본문
문제 링크
풀이
- 최댓값을 유도하기 위해선
- 양수와 음수는 서로 곱해야한다.
- 양수 묶음의 경우, 큰 수끼리 곱해야한다. (ex. 5, 4)
- 음수 묶음의 경우, 절대값이 큰 음수끼리 곱해야한다. (ex. -5, -4)
- 1 은 어떠한 경우든, 묶어서 곱셈하는 결과값보다, 개별로 덧셈하는 결과값이 더 크다.
- 0 을 개별로 더하는 것은 무의미하므로,
- 음수의 개수가 홀수일 경우, 가장 절대값이 작은 음수와 0 을 곱해주는 방식이 최댓값 유도에 좋다. (ex. -1 * 0)
- 양수와 음수는 서로 곱해야한다.
- 풀이 방법
- 양수들은 positive 벡터에 저장하고, 음수들은 negative 벡터에 저장한다.
- 0 의 개수는 개별 변수로 저장하고, 1 은 모두 총 결과값에 더해준다.
- 이후, positive 벡터는 내림차순 정렬하고, negative 벡터는 오름차순 정렬한다.
- positive 벡터의 요소가 홀수개라면(4, 3, 2), 앞에서부터 2개씩 묶어 곱셈한 결과와 가장 작은 값을 총 결과값에 더해준다.
- negative 벡터의 요소가 홀수개라면(-5, -4, -3), 앞에서부터 2개씩 묶어 곱셈한 결과를 총 결과값에 더한 뒤,
- 0 이 존재한다면 negative 벡터의 가장 큰 값(-3)과 곱해 음수를 상쇄시키고,
- 0 이 존재하지 않는다면 negative 벡터의 가장 큰 값(-3)을 바로 총 결과값에 더한다.
- 예시
- [-4, 1, -3, 1, -1, 0, 5, 1, 2] 가 입력으로 들어올 경우 아래와 같이 구분할 수 있다.
- 양수 : 5, 2
- 1, 1, 1
- 0
- 음수 : -4, -3, -1
- 따라서, 아래와 같이 최대값을 도출할 수 있다.
- (5 * 2) + 1 + 1 + 1 + ( 0 * -1 ) + (-3 * -4) = 25
- [-4, 1, -3, 1, -1, 0, 5, 1, 2] 가 입력으로 들어올 경우 아래와 같이 구분할 수 있다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 양수 저장 벡터
vector<int> positive;
// 음수 저장 벡터
vector<int> negative;
// 0 의 개수
int zero_count;
// 수열 최댓값
int result;
// 수열 최댓값 출력 함수
int greedy(){
// 양수 저장 벡터 내림차순 정렬
sort(positive.begin(), positive.end(), greater<int>());
// 음수 저장 벡터 오름차순 정렬
sort(negative.begin(), negative.end(), less<int>());
// 내림차순 정렬된 양수 저장 벡터의 요소들을 두 묶음씩 곱한 뒤, 결과값에 추가
for (int i=0; i<positive.size()-(positive.size()%2); i +=2){
// i 번째 요소와 i+1 번째 요소를 곱한 뒤, 결과값에 추가
result += positive[i] * positive[i+1];
}
// 양수 저장 벡터가 홀수일 경우, 마지막 요소가 묶음에서 제외되었기 떄문에, 마지막 요소를 결과값에 추가
if (positive.size() % 2 == 1){
result += positive.back();
}
// 오름차순 정렬된 음수 저장 벡터의 요소들을 두 묶음씩 곱한 뒤, 결과값에 추가
for (int i=0; i<negative.size()-(negative.size()%2); i +=2){
// i 번째 요소와 i+1 번째 요소를 곱한 뒤, 결과값에 추가
result += negative[i] * negative[i+1];
}
// 음수 저장 벡터가 홀수일 경우, 마지막 요소가 묶음에서 제외되었기 떄문에, 마지막 요소를 결과값에 추가
if (negative.size() % 2 == 1){
// 만약, 수열에 0 이 존재하지 않는다면, 음수 저장 벡터의 마지막 요소를, 그대로 결과값에 추가
if (zero_count == 0){
result += negative.back();
}
// 만약, 수열에 0 이 존재한다면, 음수 저장 벡터의 마지막 요소와 0 을 곱할 수 있으므로, 상쇄 가능
}
// 수열 최댓값 반환
return result;
}
int main(){
// 수열의 개수
int n;
cin >> n;
// 수열 요소 입력
for (int i=0; i<n; ++i){
int number;
cin >> number;
// 숫자가 1 보다 크다면, 양수 저장 벡터에 저장
if (number >1){
positive.push_back(number);
}
// 숫자가 1 이라면, 수열 최댓값에 추가
else if (number == 1){
result += 1;
}
// 숫자가 0 이라면, 0 의 개수 추가
else if (number == 0){
zero_count += 1;
}
// 숫자가 0 보다 작다면, 음수 저장 벡터에 저장
else{
negative.push_back(number);
}
}
// 수열 최댓값 출력
cout << greedy() << endl;
}
참고
'Algorithm > Greedy' 카테고리의 다른 글
[Greedy] 이코테 “숫자 카드 게임” Python 풀이 (0) | 2022.05.31 |
---|---|
[Greedy] 이코테 “큰 수의 법칙” Python 풀이 (0) | 2022.05.30 |
[Greedy] 백준 13305번 "주유소" C++ 풀이 (0) | 2022.02.14 |
[Greedy] 백준 10162번 "전자레인지" C++ 풀이 (0) | 2022.02.14 |
[Greedy] 백준 11000번 "강의실 배정" C++ 풀이 (0) | 2021.12.07 |
Comments