[알고연] (3주차-1) 734B. Anton and Digits

734B. Anton and Digits

Recently Anton found a box with digits in his room. There are k2 digits 2, k3 digits 3, k5 digits 5 and k6 digits 6.
Anton's favorite integers are 32 and 256. He decided to compose this integers from digits he has. He wants to make the sum of these integers as large as possible. Help him solve this task!
Each digit can be used no more than once, i.e. the composed integers should contain no more than k2 digits 2, k3 digits 3 and so on. Of course, unused digits are not counted in the sum.

이번주의 알고리즘 테마는 Greedy로, 백준에서 풀었던 브론즈 ~ 실버 하위 난이도의 문제들을 풀었다.

이 문제는 주어진 2, 3, 5, 6들을 이용하여 32와 256을 만들어 총합이 가장 크도록 선택하는 문제이다. Greedy 알고리즘을 모르더라도, 256을 우선 먼저 많이 만들고 남은 것들로 32를 만들어야 함을 알 수 있다. 교수님도 안 그러면 최대가 아니니깐! 너무 당연하다는듯이 증명하셨다. 

따라서 먼저 k2, k5, k6 중에서 가장 작은 값에 256을 곱하고 sum에 더한다. k2에서 이 값을 빼면 남은 2의 개수가 된다. 그러고나서 k2와 k3 중에서 가장 작은 값에 32를 곱하고 sum에 더하면 최종 결과를 얻을 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	long long k2, k3, k5, k6, sum;
	cin >> k2 >> k3 >> k5 >> k6;
    
	sum = min(k2, min(k5, k6)) * 256;
	k2 -= min(k2, min(k5, k6));
    
	sum += min(k2, k3) * 32;
	cout << sum << "\n";
    
	return 0;
}