문제 이해하기
길이가 N인 수열이 주어졌을 때, 그 수열의 합 구하기.
- 수열의 두 수를 묶으려 한다.
- 위치에 상관 없이 두 수를 묶을 수 있다. ( 자기 자신과 묶을 수는 없다 )
- 어떤 수를 묶게 되면, 묶은 수는 서로 “곱한 후” 수열의 합에 더해준다.
- 예시로는, 어떤 수열 {0,1,2,3,4,5} 가 주어졌을 때, 0+1+(23)+(45) = 27이 되어 최대 가 된다 는 예시를 주었지만,
- 수열이 {4,2,1,0,5 } 가 주어져도 위와 똑같이 구할 수 있다. 위치에 상관 없이 두 수를 묶을 수 있다 하였기 때문이다.
- 모든 수는
- 단 한번만 묶거나
- 한 번도 묶지 않아야 한다.
- 구해야 되는 것
- 그 합이 최대가 되게 하는 프로그램
- 수열의 크기 N은 50이하의 자연수
- 생각보다 적은 개수를 준 것을 보아하니, 어느정도 나이브 해야하는걸까?
- 정답은 항상 2^31 보다 작다 =⇒ int형으로 구할 수 있다.
문제 풀기
안 묶는게 나을 수도 있겠음.
묶으면 “곱셈”을 하게되니.. 0 뿐만 아니라 “음수” 와 “엄청 큰 양수”를 곱하면, 합을 매우 많이 감소시킬 것.
- 음수 x 양수
문제에서
- 묶는 것 끼리의 순서는 상관이 없다고 했으니 → 일단 수열을 정렬한다.
- 큰 수는 큰 수 끼리, 작은 수는 작은 수 끼리 묶는게 무조건 좋을까? ( 묶는다면! 그런 듯 )
- 음수 x 음수 ⇒ 양수가 되니 좋고
- 큰수 x 큰수 ⇒ 가장 큰 수가 나올 수 있음.
-1000 - 555 0 10
-1000 - 555 0 10 500
-1000 1 44 => 이거 안 묶는게 낫다. - 안 묶는게 나은 경우
- 음수 x 양수
- 1 x 양수
- 양수 + 1 > 양수*1
- 0(zero) x 양수
- 양수 + 0 > 양수*0(zero가 되어버림)
-1000 10 => -1000 + 10 이 -1000 x 10 보다 훨씬 나음. - 정렬 → 맨 앞에서부터, 두 수를 묶어 나간다 . 이 때, 안 묶는게 나은 경우에는 묶지 않는다.
- 묶인건지 확인하는것도 필요함.
- 매 번, 2개씩 비교해야할 듯
0 1
틀렸음
왜냐하면.
지금 양수 대역에서, 가장 작은 것부터 묶어줄 쌍을 찾아주고 있다보니
2 3 5 가 있다면, 2 + ( 3 5 ) 가 더 큰 경우인데 (23 ) + 5 를 해주고 있게 됨.*
*( 양수에 대해서도, 앞에서부터 순차적으로 접근하고 있기 때문임. )*
- 처음으로 0이 아닌 양의 정수가 나오는 곳을 찾고 → under
- 음수가 존재하는 경우 →(앞에서부터 2개씩) 0 ~ under -1 까지는 이전에 했던 방식을 사용
- 양수가 존재하는 경우 → (뒤에서부터 2개씩) n-1 ~ under +1 까지는 이전에 했던 방식을 거꾸로 하기
6
-4
-1
0
2
4
5
// 26
7
9
7
4
2
8
8
7
//158
public class Main{
public static int n;
public static int[] arr;
public static boolean[] visit = new boolean[50];
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException {
n = Integer.parseInt(br.readLine());
arr = new int[n];
for(int i =0; i<n;i++)
arr[i] = Integer.parseInt(br.readLine());
}
// 없는 경우 -> return n;
public static int findFirst(int target){
int left = 0, right = n, mid = 0;
while(left<right){
mid = (left+right)/2;
if(arr[mid]>=target)right = mid;
else left = mid + 1 ;
}
return right;
}
public static int solve() {
int i = 0, sum = 0;
Arrays.sort(arr);
int under = findFirst(1); // 첫 번째 양수의 위치
// 양의 정수가 존재하는 경우
if (under != n) {
// 양수
for (i = n - 1; i > under; i--) {
if (visit[i]) continue;
// 다음수가 0 또는 1인 경우 -> 다음 수와 묶지 않는다
if (arr[i - 1] == 0 || arr[i - 1] == 1) {
sum += arr[i];
} else {
sum += (arr[i] * arr[i - 1]);
visit[i - 1] = true;
}
visit[i] = true;
}
// for 문에서, 양의 수 중 첫 번째 수까지 도달하지 못한 경우
if (!visit[under]) sum += arr[i];
}
// 음수가 존재하는 경우
if ( under > 0) {
for (i = 0; i < under - 1; i++) {
if (visit[i]) continue;
// 다음수가 양수 -> 다음수와 묶지 않는다
if (arr[i + 1] > 0) {
sum += arr[i];
}
// Otherwise -> 다음수와 묶어준다 ( 묶인 수는 다음 계산의 대상이 되지않는다 ->visit = true )
else {
sum += (arr[i] * arr[i + 1]);
visit[i + 1] = true;
}
visit[i] = true;
}
if (!visit[under - 1]) sum += arr[under - 1];
}
return sum;
}
public static void main(String[] args) throws IOException{
setting();
System.out.println(solve());
}
}좀 더 정리된 풀이 (다른 분 풀이)
- 정렬 한다 .
- 둘 다 음수인 경우만 더해주고 ( 아래에서부터 시작 )
- 둘 다 음수가 아니게 되면, break ( 자연스럽게, 처음으로 양수가 나오는 지점에서 break되는거임)
- 둘 다 양수인 경우만 더하기
- 둘 다 양수가 아닌 곳에서 break 되는 거임
—> 이러면, 자연스럽게, 남은 부분들이 생기는데, 이들은 “+” 연산을 해 주면 되는 것들이 되어버림. ( 이러면 visit도 확인할 필요가 없음)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int ans = 0;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int left = 0;
int right = n - 1;
for (; left < right; left += 2) {
if (arr[left] < 1 && arr[left + 1] < 1) {
ans += arr[left] * arr[left + 1];
} else {
break;
}
}
for (; right > 0; right -= 2) {
if (arr[right] > 1 && arr[right - 1] > 1) {
ans += arr[right] * arr[right - 1];
} else {
break;
}
}
for (; right >= left; right--) {
ans += arr[right];
}
System.out.println(ans);
}
}