[Java] 백준 12931번 두 배 더하기

그리디 문제입니다.

0으로 이루어진 A배열과 값이 있는 B배열이 주어집니다.
규칙에 따라 B배열을 만들 때 최소 횟수를 출력해야합니다.

1. A배열에서 하나의 값을 1 올린다.
2. A배열 전체에 2를 곱한다.

경우의 수가 많아 보이지만 그리디로 처리할 수 있습니다.
각 값을 기준으로 0을 만들때 1번과 2번을 몇번 사용해야하는지 구해줍니다.

2로 나눌 수 있는 경우 2로 나누어주고 2번 사용에 대해서 카운팅 해줍니다.
2로 나눌 수 없는 경우 1을 빼주고 1번 사용에 대해서 카운팅 해줍니다.

그러면 각 값을 최소한으로 만들 수 있느 수가 나옵니다.

곱셈의 경우 (2번 경우) 모두 같이 사용할 수 있으므로 각 값들에 대해서 최대로 많이 사용한 값만 있으면 됩니다.
덧셈의 경우 (1번 경우) 각자 사용하므로 누적으로 값을 계산해줍니다.

1번 2번 경우에 대해서 구한 값을 더해서 출력해주었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int result = 0;
    ArrayList<Integer> al = new ArrayList<>();

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      int num = Integer.parseInt(st.nextToken());
      if (num == 0) {
        continue;
      }
      al.add(num);
    }

    int mulMax = 0;
    int addMax = 0;
    for (int i = 0; i < al.size(); ++i) {
      int mulCnt = 0;
      int addCnt = 0;

      int num = al.get(i);
      while (num > 1) {
        if (num % 2 == 0) {
          num /= 2;
          ++mulCnt;
        } else {
          --num;
          ++addCnt;
        }
      }
      ++addCnt;

      mulMax = Math.max(mulMax, mulCnt);
      addMax += addCnt;
    }

    result = mulMax + addMax;

    bw.write(result + "\n");
    bw.close();
  }
}