[백준] 12931번 : 두 배 더하기(JAVA)

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

12931번: 두 배 더하기

풀이

입력받은 숫자의 크기를 입력받고, 수를 입력받았을 때 전부 0이였던 배열이 몇번 연산해야 입력받은 수만큼 되는지 계산하는 문제입니다.

 

규칙

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

이럴경우 A --> B 보다 역으로 B --> A(전부 0인 배열) 을 생각하시면 됩니다.

모든 수가 0일때 마무리되도록 하기 위해서 1개1개 다 비교하면서 체크하는것보다 sum 변수를 만들어 합을 구하고 시작합니다.

sum이 0이 될때까지 반복하면서, 입력받은 배열의 수중 2로 나누었을때 1인 경우의 수를 계산하면서 1을 빼줍니다.

1로 남는 수의 갯수를 sum에서 빼줍니다. 그리고 answer에 그 갯수를 더해줍니다.

2로 나누었을때 1로 남는 수가 없을 경우 answer++을 해주면서 2로 나누어지는 수 전부 2로 나눠주면 됩니다.

 

해당 연산을 반복하였을 경우 최소한의 횟수로 특정배열을 만들 수 잇는 횟수가 나오게 됩니다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		int size = Integer.parseInt(br.readLine());
		
		int[] n = new int[size];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int sum = 0;
		for(int i = 0; i < size; i++) {
			n[i] = Integer.parseInt(st.nextToken());
			sum += n[i];
		}
		
		int answer = 0;
		while(sum != 0) {
			int num = 0;
			for(int i = 0; i < size; i++) {
				if(n[i] % 2 == 1) {
					n[i]--;
					num++;
				}
			}
			
			if(num > 0) {
				sum -= num;
				answer += num;
			}
			else {
				for(int i = 0; i < size; i++) {
					n[i] /= 2;
				}
				sum /= 2;
				answer++;
			}
		}
		System.out.print(answer);
	}
}