[Algorithm] Greedy 30 (백준) - 에이젠

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

10610번: 30

공략

10^5개의 숫자로 구성된다라는 말은 예제를 보면 10^5보다 큰 숫자가 있었기에 자리수가 10^5 자리까지 있다는 것을 알 수 있었습니다. 완전탐색으로는 역시 풀 수 없겠죠.

 

1. 숫자 안에 0 이 꼭 필요하다.

 30의 배수이기 때문에 0이 없으면 안 되는 것을 알 수 있었습니다.

1의자리 빼고는 3의배수가 나오도록 가장 큰 수를 찾아야하는데...

결국 힌트를 찾아보았습니다.

2. 모든 자리수 합이 3의 배수.

모든 자리수의 합이 3의 배수가 되면 된다고 하는군요?

쉽지 않네요 ㅎㅎ.

 

모든 자리수의 합이기 때문에 직접 순서를 다시 배열해볼 필요가 없겠죠. 

0이 있는것을 확인하고 나머지 숫자를 합해서 3의 배수가 맞는지 진위판정만 해주면 되겠습니다.

그리고 제일 큰수가 되기 위해서 내림차순으로 정렬합니다.

 

 

 

import java.util.*;

public class Main {

  // 0이 여러개 있는경우?
  static String N;
  static Scanner sc = new Scanner(System.in);
  static Integer[] arr;
  static StringBuilder sb = new StringBuilder();

  static void input() {
    N = sc.next();
  }

  static boolean isThereZero() {
    for (int i = 0; i < N.length(); i++) {
      if (N.charAt(i) == '0') {

        String frontStr = N.substring(0, i);
        String endStr = N.substring(i + 1);

        N = frontStr + endStr; // 0 제거 (나중에 추가해주어야함.)

        return true;
      }
    }
    return false;
  }

  static boolean isPossible30() {

    int total = 0;
    arr = new Integer[N.length()];

    for (int i = 0; i < N.length(); i++) {
      total = total + N.charAt(i) - '0';
      arr[i] = N.charAt(i) - '0';

    }
    if (total % 3 == 0) {
      return true;
    }
    return false;
  }

  static void findAns() {

    if (isThereZero()) {
      if (isPossible30()) {
        Arrays.sort(arr, Collections.reverseOrder());
        Arrays.toString(arr);

        String output = "";
        for (int i = 0; i < N.length(); i++) {
          output = output + String.valueOf(arr[i]);
        }
        output = output + "0";
        System.out.println(output);

      } else {
        System.out.println(-1);
      }

    } else {
      System.out.println(-1);
    }

  }

  public static void main(String[] args) {
    input();
    findAns();
  }

}