[G5] 백준 12931번 두 배 더하기 C++ 그리디 알고리즘

리뷰

 

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

배열에 있는 모든 값을 두 배 시키는 연산을 효율적으로 사용하는게 중요한 문제

 

 

전역 변수

• n : 배열의 길이를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 변수 md, mc를 0으로 초기화한다.
2. n개의 원소를 변수 x에 입력 받아주고, 변수 d를 0으로 초기화한다.
3. x가 0보다 클 경우를 조건으로 하는 while루프를 수행한다.
4. x를 2로 나누었을때 나머지가 존재한다면 x를 감소시키고 mc를 증가시킨다.
5. x를 2로 나누어 떨어진다면 x를 2로 나누고 d를 증가시킨다.
6. md를 d와 비교하여 더 큰값으로 갱신하고 위 로직을 반복한다.
7. mc와 md를 더한 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 원소의 값이 1000보다 작거나 같으므로 위 같이 1씩 감소시키는 로직을 사용하였다.
2. 만약 수의 범위가 더 클 경우 비트 연산을 통한 풀이를 통해 연산을 줄일 수 있다.

 

정답 코드

#include<iostream>
using namespace std;

int n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	int md = 0, mc = 0;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;

		int d = 0;
		while (x > 0) {
			if (x % 2) {
				--x;
				++mc;
			}
			else {
				x /= 2;
				++d;
			}
		}

		md = max(md, d);
	}
	cout << mc + md;
}