if문 처리가 굉장히 어마어마하게 귀찮았던문제
마치 ' 두 박스 ' 를 연상시킨다
좀 더 고민하면 잘 줄여낼수있을거같긴한데...
https://www.acmicpc.net/problem/1744
1744번: 수 묶기
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에
www.acmicpc.net
#include <stdio.h>
#include <algorithm>
int arr[10001] = {0};
int main(){
int n,ans=0;
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &arr[i]);
std::sort(arr, arr+n);
for(int i=n-1; i>=1; i--){
if((arr[i-1]>0 && arr[i-1]!=1) || (arr[i]<=0 && arr[i-1]<0 && !i%2==0)){
arr[i] *= arr[i-1];
arr[i-1] = 0;
i--;
}
}
for(int i=0; i<n; i++){
ans += arr[i];
}
printf("%d", ans);
return 0;
}
수들을 입력을 받아서
곱하기 편하게 정렬을 시켜줬다.
복잡한 저 if문을 설명하자면,
정렬시켜준 후에 || 으로 크게 두부분으로 나뉘게 되는데,
그 중 앞부분은 두 값이 전부 양수일때이다.
arr[i-1]이 양수인지를 확인하는데, 정렬이 되어있으므로 arr[i]는 항상 arr[i-1]보다 큼이 보장된다.
그래서 굳이 arr[i]도 확인할필요는 없고,
arr[i-1]이 1인경우 곱하는것보다 더하는경우가 더 값이 크므로
그부분도 &&로 묶여서 잘 처리되있다.
뒷부분은 두 수가 0이거나 음수인 파트이다.
음수끼리 곱해서 양수를 만들거나 음수x0으로 0을 만들어주는게 최대값을 만들 수 있으므로
arr[i]<=0 && arr[i-1]<0 이부분은 음수인지를 확인해주는 파트가 되겠다.
그런데 입력값이
5
-1 -2 0 0 0처럼 들어오는경우에는
-1 x -2가 최적해이지만
0 x -1을 해버려서 -2를 처리하지 못하는 문제가 발생했고,
이는 !i%2==0 을 통해 남은 음수가 얼마나 되는지 판별함을 통해
음수가 짝수개 남아있으면 0과 곱하지 않게 해주었다.
