[Algorithm] Greedy 수 묶기(백준) - 에이젠

 

 

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

1744번: 수 묶기

 

실수

처음에 입출력 예제의 예상 값과 답이 다르게 나오길래 
문제를 잘못이해했나? 하고 헤맸는데 알고보니 첫째줄은 수열의 길이를 입력하는 것인데 첫째줄까지 연산에 포함시키는 바보짓을 했네요. ㅎㅎ

공략

 

알고리즘 중급 1/3 의 그리디 연습 문제입니다.

1. 정렬 수행.

 

2. 묶는다 

    -> 큰 양수 x 큰 양수 (1이 아닌 양수)

    -> 작은 음수 x 작은 음수

    -> 작은 음수 x 0

 

3. 덧셈 수행. 

import java.util.*;

public class Main {

  static int N;
  static Scanner sc = new Scanner(System.in);
  static ArrayList<Integer> arr = new ArrayList<>();
  static boolean[] visited;

  static void input() {
    N = sc.nextInt();
    for (int i = 0; i < N; i++) {
      int num = sc.nextInt();
      arr.add(num);
    }

    Collections.sort(arr);
    visited = new boolean[N];
  }

  
  static void bind() {
    int total = 0;

    int bindingNum = 0;

    // 작은 음수 x 작은 음수 or 제로
    for (int i = 0; i < arr.size(); i++) {

      if (visited[i] == false && arr.get(i) <= 0 && bindingNum < 0) { // 0이나 음수인 두번째를 찾았다면
        // 곱셈 연산
        int result = bindingNum * arr.get(i);
        total = total + result;
        visited[i] = true;
        bindingNum = 0;

      } else if (visited[i] == false && arr.get(i) < 1) {
        bindingNum = arr.get(i);
        visited[i] = true;
      }
    }
    total = total + bindingNum;
    bindingNum = 0;


    // 큰 양수 x 큰 양수 (1이 아닌 양수)
    for (int i = arr.size() - 1; i >= 0; i--) {
      if (visited[i] == false && arr.get(i) > 1 && bindingNum > 0) {
        // 곱셈 연산
        int result = bindingNum * arr.get(i);
        total = total + result;
        visited[i] = true;
        bindingNum = 0;
      } else if (visited[i] == false && arr.get(i) > 1) {
        bindingNum = arr.get(i);
        visited[i] = true;
      }

    }
    total = total + bindingNum;
    for (int i = 0; i < arr.size(); i++) {
      if (visited[i] == false) {
        total = total + arr.get(i);
      }
    }
    System.out.println(total);

  }

  public static void main(String[] args) {

    input();
    bind();
  }
}