[Gold IV] 수 묶기 - 1744
성능 요약
메모리: 12968 KB, 시간: 116 ms
분류
많은 조건 분기(case_work), 그리디 알고리즘(greedy), 정렬(sorting)
문제 설명
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.
풀이
처음에는 N*N개의 가능한 곱을 모두 구해서 정렬한 후, 곱이 큰 값 중에 아직 리스트에 추가되지않은 값들을 차례대로 더하면서 값을 구했다.
/**
* 7
* 3
* 2
* 1
* 1
* 0
* 0
* -3
* ans = 8
* 0*0보다 0*-3이 우선해야 한다
*/
그러면 위의 경우처럼 0*-3이 포함되어야 하는데 0*0이 먼저 포함되는 문제가 생겼다.
그래서 0이하의 수와 1 이상의 수를 리스트를 나누고, 0 이하의 수는 작은 순서대로 곱을 더해나가고 1 이상의 수는 큰 순서부터 곱을 더하였다.
현재 수와 다음 수의 곱이 두 수의 합보다 큰 경우에만 곱을 더해주고, 합이 더 크다면 현재 수만 더하고 다음 수를 다시 확인하였다.
private static void getSum(List<Integer> plusNum, int idx) {
while (idx < plusNum.size()) {
if (idx + 1 < plusNum.size()) {
int curr = plusNum.get(idx);
int next = plusNum.get(idx + 1);
if (curr * next > curr + next) {
ans += curr * next;
idx += 2;
} else {
ans += curr;
idx++;
}
} else {
ans += plusNum.get(idx);
idx++;
}
}
}
전체 코드
package BOJ.Gold.g4;
import java.util.*;
public class BOJ_1744_수묶기 {
static int N;
static int ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
// 0 이하
// 1 이상
List<Integer> minusNum = new ArrayList<>();
List<Integer> plusNum = new ArrayList<>();
for (int i = 0; i < N; i++) {
int num = sc.nextInt();
if (num >= 1) plusNum.add(num);
else minusNum.add(num);
}
Collections.sort(minusNum); // 작은수부터
plusNum.sort(Comparator.reverseOrder()); // 큰수부터
int idx = 0;
getSum(minusNum, idx);
getSum(plusNum, idx);
System.out.println(ans);
}
private static void getSum(List<Integer> plusNum, int idx) {
while (idx < plusNum.size()) {
if (idx + 1 < plusNum.size()) {
int curr = plusNum.get(idx);
int next = plusNum.get(idx + 1);
if (curr * next > curr + next) {
ans += curr * next;
idx += 2;
} else {
ans += curr;
idx++;
}
} else {
ans += plusNum.get(idx);
idx++;
}
}
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 12738 - 가장 긴 증가하는 부분 수열 3 (자바 Java) (0) | 2023.02.20 |
---|---|
[백준] 15684 - 사다리 조작 (자바 Java) (0) | 2023.02.05 |
[백준] 2193 - 이친수 (자바 Java) (0) | 2023.01.21 |
[백준] 17182 - 우주 탐사선 (자바 Java) (0) | 2023.01.13 |
[백준] 15591 - MooTube (Silver) (자바 Java) (0) | 2023.01.11 |