[백준 12931] 두 배 더하기 C++

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

12931번: 두 배 더하기

문제풀이

 

 

0으로 채워진 배열에서 

1. 배열 중 하나의 값을 1 증가

2. 배열의 모든 값을 두배 시킴

 

의 방법을 사용해서 입력으로 주어진 배열을 찾는데 최소 횟수를 구하는 문제인데, 

 

역으로 입력으로 주어진 배열에서 0으로 채워지게 하려면 최소 몇번을 구해야하는지로 바꿔서 풀었습니다.

 

다행이도, 2배와 1추가는 홀짝으로 구분할 수 있기 때문에, 

 

모든 배열이 0을 만나지 않는 한 무한while문을 돌도록 만들었고, 모든 배열을 0을 만났을 때 break해주어 무한루프에서 빠져나올 수 있게 만들었습니다.

 

제가 짠 알고리즘은 어떻게든 0으로 만들어지기때문에 무한루프를 돌 경우는 없습니다. 

 

그래서, 배열의 전부 0인지 확인하는 FLAG를 사용했습니다.

 

그리고 2로 나눈 나머지가 0이 안된다면, +1이 되어있는것과 마찬가지기 때문에 그 해당 배열을 -1을 해주어 카운트를 증가시켜줬고요. 배열 한번만 지나면 홀수를 짝수로 다 바꿔주기 때문에 바꿔줄 때마다 카운트를 하고,

 

그 다음부터 2로 나눌 때는, 2로 다 나눈 연산을 계속해서 하고 마지막 1이 되었을 때 또, -1을 해줌으로써 0으로 만들면 됩니다. 

 

모든 배열이 0으로 만들어지면 while 루프문을 빠져나와 카운트를 세었던 값을 출력하면 됩니다.

 

저의 알고리즘에서 중요한 것은 모든 배열이 0 인데, 바로 2로 나누어 카운트를 1추가 할 수 있기 때문에, 

모든 배열이 0일 때, 모든 배열을 2로 나누는 연산으로 들어가지 않고, 바로 zero FLAG에서 while문을 탈출하도록 만들었습니다.

 

전체 코드는 다음과 같습니다.

 

#include <iostream>
#include <deque>

using namespace std;

#define input_max 50 + 1


deque<int> b(input_max);

int n;

int result;

void solution() {

	cin >> n; 
	

	for (int i = 0; i < n; i++) cin >> b[i]; // 입력


	bool null_FLAG = false;     //모든 배열이 0인지확인하는 FLAG, default는 true
	bool allEven_FLAG = false;  // 모든 배열이 짝수인지 확인하는 FLAG, default는 true


	while (1) {

		null_FLAG = true;       // default true 설정
		allEven_FLAG = true;    // default true 설정

		for (int i = 0; i < n; i++) {

			if (b[i]) null_FLAG = false;     //n번까지 돌았는데 모든 배열이 0이면 true를 계속 유지할 것임. 값이 있는 걸 찾으면 false표시

			if (b[i] % 2) {       // 배열의 값이 짝수가 아닐 때
				result++;         // 1을 빼주는 연산을 해야하기 때문에 카운트 1증가
				b[i] -= 1;        // 1을 빼줌
				allEven_FLAG = false;   // 모든 배열이 짝수가 아니라는 의미, false
			}
		}

		if (null_FLAG) break;          // 모든 배열이 0일 때 즉, 값이 있는 것을 발견하지 못했을 때 while루프를 빠져나옴


		if (allEven_FLAG) {
			for (int i = 0; i < n; i++) b[i] /= 2;        // 모든 배열의 값이 짝수일 때, 2로 나누어주고 카운트 1증가
			
			result++;
		}
	}


	cout << result << '\n';
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solution();

	return 0;
}