[java 백준]골드 4/ 1744번 수묶기

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static long cnt = 0;
 
    public static int[] arr;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
 
        }
        Arrays.sort(arr);
        // 1은 곱해주는것보다 더해주는게 이득
 
        // 음수만 (앞에서부터)
        // 0포함
 
        int left = 0;
        int right = n - 1;
        cnt = 0;
        for (; left < right; left += 2) {//등호 붙이면 안됨, 인덱스 bound 넘어감
            if (arr[left] < 1 && arr[left + 1] < 1) {
                cnt += arr[left] * arr[left + 1];
            } else {
                break;
            }
        }
 
        // 양수만 (뒤에서부터)
        // 양수는 1보다 큰애만
 
        for (; right > 0; right -= 2) {
            if (arr[right] > 1 && arr[right - 1] > 1) {
                cnt += arr[right] * arr[right - 1];
            } else {
                break;
            }
        }
 
        for (; right >= left; right--) {
            cnt += arr[right];
        }
 
        System.out.println(cnt);
    }
 
}

문제를 풀면서 중요한 부분 

최대 값이 나오기 위해서는 수를 묶을 때

 

(1보다 양수 *1보다 양수)

(0*음수)

(음수*음수) 여야 한다.

1의 경우 1과 양수를 곱해주는것보다 1과 양수를 더해주는게 더 크다. 음수는 굳이 말할 필요도 없다.

 

이렇게 조건 분기를 해주고, 수를 정렬하면 앞에는 음수또는 양수들 중 작은 수 뒤에는 양수들이 자리할 것 이다.

 

그러면 앞에 있는 수부터 탐색해주는(사실상 음수를 묶어주기 위함) for문은

 if (arr[left] < 1 && arr[left + 1] < 1) {

                cnt += arr[left] * arr[left + 1];

            } 

를 사용해서 두 수가 1보다 작은 경우에만 묶어준다.

 

뒤에 있는 수부터 탐색해주는 (사실상 1보다 큰 양수를 묶어주기 위함 ) for문은

 if (arr[right] > 1 && arr[right - 1] > 1) {

                cnt += arr[right] * arr[right - 1];

            }

를 사용해서 두 수가 1보다 큰 경우에만 묶어준다.

 

그리고 1과 같이 남는 수들은

for (; right >= left; right--) {

            cnt += arr[right];

        }

--> 이걸 이용해 그냥 더해주는 걸로 처리한다.

 

헛발질

 

1) 문제를 풀면서 크게 잘못 생각한게 있었는데 두개씩 묶는다는 것을 두개씩 묶는걸 두번만 가능하다고 이해한거였다. 나도 내가 왜 이렇게 이해한지 모르겠다 ㅋㅋㅋ 그래서 스스로 문제를 더 어렵게 만들고 있었다.

두개씩 묶기만 하면 그 개수는 제한이 없다...!

 

2) 이건 내가 처음에 작성한 코드인데 질문에 있는 반례를 넣어봐도 대부분 맞았다. 어디서 틀린지 모르겠어서 나중에 찾으면 다시 확인하려고 첨부해둔다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
    public static long cnt = 0;
 
    public static int[] arr;
 
    public static long tie() {
        cnt = 0;
        int i = 0;
 
        while (i < n) {
            if (i < n - 1) {
                if (arr[i] > 1 && arr[i + 1] > 1) {
                    cnt += arr[i] * arr[i + 1];
                    i += 2;
 
                    continue;
                } else if (arr[i] <= 0 && arr[i + 1] <= 0) {
                    cnt += arr[i] * arr[i + 1];
                    i += 2;
 
                    continue;
                }
            }
            if (i < n) {
                cnt += arr[i];
                i++;
            }
        }
 
        return cnt;
 
    }
 
    public static long reverseTie() {
        cnt = 0;
        int i = n - 1;
        while (i >= 0) {
            if (i >= 1) {
                if (arr[i] > 1 && arr[i - 1] > 1) {
                    cnt += arr[i] * arr[i - 1];
                    i -= 2;
 
                    continue;
                } else if (arr[i] <= 0 && arr[i - 1] <= 0) {
                    cnt += arr[i] * arr[i - 1];
                    i -= 2;
 
                    continue;
                }
 
            }
            if (i >= 0) {
                cnt += arr[i];
                i--;
            }
 
        }
        return cnt;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
 
        }
        Arrays.sort(arr);
 
        // 스스로 엄청 어려운 조건을 넣고 있었음
        // 묶는건 횟수 제한 없음 --> 난 두번인줄 알았
 
        if (n == 1) {
            System.out.println(arr[0]);
        } else {
            long ans = tie();
            long ans2 = reverseTie();
            if (ans >= ans2) {
                System.out.println(ans);
            } else {
                System.out.println(ans2);
            }
        }
 
    }
 
}

 

 

참고사이트

for문을 돌려서  음수*음수  1보다 큰 양수*1보다 큰 양수 끼리 하는 방법은 다른 사람의 코드를 참고했다.

 

https://mygumi.tistory.com/220

백준 1744번 수 묶기 :: 마이구미