[백준 1744] 수 묶기 -JAVA //le_effort

수 묶기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7531	2095	1701	27.872%

문제

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(23)+(45) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열의 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력

수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

예제 입력 1 복사

xxxxxxxxxx
4
-1
2
1
3

예제 출력 1 복사

xxxxxxxxxx
6

힌트

(-1)+1+(2*3)=6

 

풀이

그리디 알고리즘

 

그런데 녹록치 않았다. 그리디에 대한 내 고정관념도 많이 박혀 있었고 여러 예외케이스 들을 처리 하는게 오래걸렸다.

 

그리디라고 하면 무조건 정렬 후 큰 수 부터 묶어서 더하면 되겠지 라고 생각했는데

음수 값이 들어 올 경우 그게 성립이 안됐다.

예제에 있는 tc값은 -1 , 2, 1, 3 이 값으로 들어오고 이를 내림차순으로 정렬하면

3 2 1 -1

이를 양수 값만 2개씩 묶어서 계산하면 3x2 +1 -1 = 6

하지만 이렇게 양수만 2개로 묶고 음수는 그냥 더하면 될 거라 생각 했던게 편협한 사고 였다.

 

이 문제를 풀려면 3가지로 나눠야 한다.

1. 1보다 큰 양수인 경우
2. 1인 경우
3. 음수인 경우

 

각각의 케이스 별로 나눠서 예를 들어보겠다

1. 1보다 큰 양수의 경우

이는 너무나도 당연한 것이라 대부분 이걸 생각 했을 것이다.

양수끼리 큰 것 끼리 묶어서 곱하는 행위는 당연히 최대값이 나온다

나는 내림차순으로 진행했고 현재 숫자 기준 다음 숫자가 인덱스에서 벗어나지 않고 1이 아니라면 곱해주었다.

 

2. 숫자가 1인 경우

이 경우 또한 나는 처음에 생각하지 못했다.

입력이 n=2 값 1,2 가 들어온다고 생각해보자

양수 2개끼리 묶고 곱하면 2가 나온다

하지만 묶지 않고 더하면 3이 나온다

그렇다, 숫자 1은 x라는 숫자랑 곱하면 무조건 x가 나오고

더하면 x+1 이 나오므로 숫자가 1일 경우에는 곱하지 않고 더해줘야 한다.

그래서 나는 따로 one 이라는 변수를 만들어줘 1일 경우에 ++ 를 시켜주고

최종값에서 더했다.

 

3. 음수인 경우

이 또한 생각하지 못해(편협한 사고방식 ㅠ) 틀렸었다

입력이 n=3 들어오는 값이 -6, -5, -1 일 경우

내 기존 풀이방식대로 내림차순으로 정렬을 한 다면

-1,-5,-6 이렇게 정렬된다. 이를 반복문의 흐름대로 묶는다면

-1 x -5 + (-6) 을 하면 -1이 나오고

-6x-5 + (-1) 을 하면 29가 나온다.

즉 음수 일 경우 내림차순으로 정렬을 했을 경우 뒤에서부터 다시 반복문을 통해 2개씩 묶어줘야 한다.

 

그리고 나는 해당 숫자를 사용했다는 의미인 visited 배열을 만들었다.

그 이유는 n = 5이고

2,1,-1,-2,-3 이라고 했을 때 (i=0 부터 시작이라 가정)

i =0 : 숫자 2

i= 1 : 숫자 1 (i가 0일때 다음숫자가 인덱스 범위 안에 들어오지만 1이라 패스)

그 후 계속진행...

이렇게 진행되면 숫자2는 값을 활용하지 못하고 계산이 끝나게 되므로

모든 계산이 끝나고 나면 방문하지 않은 부분은 더해주었다.

나는 기본적으로 모든 수를 일단 내림차순으로 정렬 했다.

배열은 기본적으로 오름차순 밖에 지원을 해주지 않아 따로 정렬을 했다.

 

전체코드

xxxxxxxxxx
import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static Node arr[];
    static long ans = 0;
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        arr = new Node[n];
        visited = new boolean[n];
        for(int i=0; i<n; i++) {
            int num = Integer.parseInt(br.readLine());
            arr[i] = new Node(num);
        }
        Arrays.sort(arr);
        int cnt =0;
        long tmp= 1;
        int one = 0;
        
        
        for(int i=0; i<n; i++) {
            if(arr[i].num>1) {      // 양수 일 때
                if(i+1<n && arr[i+1].num>1) {   //인덱스 범위 안 벗어 날 때
                    ans+=(arr[i].num * arr[i+1].num);
                    visited[i] =true;
                    visited[i+1]=true;
                    i+=1;
                }
            }
            else if(arr[i].num==1) {     //1 일때는 곱하는 것 보다 무조건 더하는게 좋음
                one++;
                visited[i]=true;
            }
            else {  // 음수 일 때  -1 -5 -6 이렇게 정렬 돼 있을꺼
                for(int j= n-1; j>=i; j--) {    
                    if(j-1 >=i) {
                        ans+=(arr[j].num * arr[j-1].num);
                        visited[j]=true;
                        visited[j-1]=true;
                        j-=1;
                    }
                    else {
                        visited[j]= true;
                        ans+=arr[j].num;
                    }
                }
                i+=n;   // 강제적으로 반복문 끝냄
            }
        }
        
        if(one !=0) {
            ans+=one;
        }
        for(int i=0; i<n; i++) {    
            if(!visited[i]) {
                ans+=arr[i].num;
            }
        }
        System.out.println(ans);
    }
}
class Node implements Comparable<Node>{
    int num;
    Node(int num){
        this.num=num;
    }
    public int compareTo(Node o) {
        return o.num-this.num;
    }
}