[Baekjoon] 12931_두 배 더하기

Gold V

문제(출처: https://www.acmicpc.net/problem/12931)

---

< 두 배 더하기 >

 

문제 풀이 

 

배열 B를 이용하여

1) 배열에 있는 값 하나를 1 감소시키기

2) 배열에 있는 모든 값을 2로 나누기

두 가지 연산을 수행하여 모든 값이 0인 배열을 만든다.

 

 my solution (Java)

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

public class _12931_ { // 두 배 더하기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		int arr[] = new int[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int answer = 0;
		int zero = 0;
		boolean flag = false;

		while (zero != n) {
			zero = 0;
			flag = false;

			for (int i = 0; i < n; i++) {
				if (arr[i] == 0) {
					zero += 1;
				}
			}
			if (zero == n) {
				break;
			}
			for (int i = 0; i < n; i++) {
				if (arr[i] % 2 == 1) {
					arr[i] -= 1;
					answer += 1;
				}
			}
			for (int i = 0; i < n; i++) {
				if (arr[i] != 0 && arr[i] % 2 == 0) {
					if (!flag) {
						flag = true;
						answer += 1;
					}
					arr[i] /= 2;
				}
			}
		}
		System.out.println(answer);
	}
}

변수)
n : 배열의 크기
arr : 배열 B 값
answer : 최소 연산 횟수
zero : 배열의 값이 0인 개수

 

배열의 크기를 입력받는다. 배열의 크기만큼 배열 B에 들어있는 원소를 입력받아 저장한다. 배열의 모든 값이 0일 때까지 다음 과정을 반복한다.

1) 배열 전체를 탐색하며 모든 값이 0인지 확인한다. 0이라면 종료

2) 2로 나누어 떨어지지 않는다면 1을 감소시키며 answer을 1 증가시킨다.

3) 배열에 있는 모든 값을 2로 나누며 answer을 1 증가시킨다.

최소 연산 횟수를 출력한다.

---

---