Baekjoon 12931 두 배 더하기 JAVA

12931번: 두 배 더하기

문제

모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다.

• 배열에 있는 값 하나를 1 증가시킨다.
• 배열에 있는 모든 값을 두 배 시킨다.

배열 B가 주어졌을 때, 배열 A를 B로 만들기 위한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄에는 배열 B에 들어있는 원소가 공백으로 구분해서 주어진다. 배열에 B에 들어있는 값은 0보다 크거나 같고, 1,000보다 작거나 같다.

출력

첫째 줄에 배열 A를 B로 바꾸기 위한 최소 연산 횟수를 출력한다.

풀이

A에서 B로 찾아가는 방법이 아닌 B에서 A로 찾아가는 방법을 사용한다.

문제의 조건에 따라서 배열의 있는 값 하나를 1 증가시키는 동작은 무조건 연산을 해야하는 동작이기에

1이 더해지는 즉, 1씩 감소하는 동작에 대해서는 연산의 수를 증가시킨다.

모든 배열에 2를 곱하는 연산은 한번의 동작만으로 모든 배열에 영향을 끼치기에,

배열의 값을 하나씩 찾아가면서 가장 많이 사용한 *2 연산의 갯수를 찾아서 최종 연산횟수에 더한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), ans=0, maxt=0;;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			// 주어진 연산을 반대로 수행해서, 어떤 값이 주어질때 역으로 0으로 만들기 위한 연산횟수를 카운팅한다
			int b=Integer.parseInt(st.nextToken()), temp=0;
			while(b>0) {	// 입력받은 b배열의 값이 0보다 더 클때 계속 반복
				if(b%2==1) {	// 1번연산은 값 하나를 1증가 시키는 것은 개별적인 동작이기에, 직접 ans에 접근해 카운팅을 추가
					ans++;
					b--;		// 역을 접근하기에, 값을 1씩 빼준다.
				}
				else {		// 2번연산은 값을 두 배 시키기 때문에, 역연산으로 값을 2씩 나누어준다
					b/=2;
					temp++;	// 나누기 연산은 배열 전체에 대해 연산을 하기에, 카운팅을 해서 가장 많이 사용한 횟수를 출력
				}
			}
			maxt=Math.max(maxt, temp);
		}
		System.out.println(ans+maxt);
	}

}