[백준] 1744번 수묶기

1744번: 수 묶기

문제 이해하기

길이가 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);

    }
}