# [Gold V] 두 배 더하기 [문제링크](https://www.acmicpc.net/problem/12931) ## 문제 설명 <p>모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다.</p> <ul> <li>배열에 있는 값 하나를 1 증가시킨다.</li> <li>배열에 있는 모든 값을 두 배 시킨다.</li> </ul> <p>배열 B가 주어졌을 때, 배열 A를 B로 만들기 위한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 50)</p> <p>둘째 줄에는 배열 B에 들어있는 원소가 공백으로 구분해서 주어진다. 배열에 B에 들어있는 값은 0보다 크거나 같고, 1,000보다 작거나 같다.</p> ## 출력 <p>첫째 줄에 배열 A를 B로 바꾸기 위한 최소 연산 횟수를 출력한다.</p> ## 풀이 #### 배열을 거꾸로 0으로 만드는 경우로 생각해보면 그리디하게 접근 할 수 있습니다. #### 1번 연산: 배열에 있는 값 하나를 1 증가시킨다. #### 2번 연산: 배열에 있는 모든 값을 두 배 시킨다. #### 1번 연산을 잘 배치하면 총 2번 연산 횟수가 2번 연산의 최대 횟수와 동일하다는 것을 알 수 있습니다. #### 따라서 최소 연산 횟수 = 1번 연산 횟수의 합 + 2번 연산의 최대 횟수 라는 것을 알 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int maxDepth=0, plusCnt=0; // 최대 2번 연산의 횟수, 1번 연산의 횟수의 합 while(n--) { int val; cin >> val; int curDepth=0; while(val) { while(val%2==0) { val/=2; curDepth++; } val--; plusCnt++; } maxDepth = max(maxDepth, curDepth); } cout << maxDepth+plusCnt; } ```