[알고리즘 문제] - C++ 그리디 알고리즘 문제 : 큰 수의 법칙

입력 조건 :  N , M, K N=배열 개수 M=몇 번 더할 수 있는지 K=중복사용 입력 예시 : 5 8 3                 2 4 5 4 6 출력 예시 : 46

배열에 숫자들을 입력받은 후, 이 숫자들을 이용하여 가장 큰 합을 만들어라..

---

즉, 가장 큰수와 그다음 큰수를 이용하여 해결 할 수 있는 문제로 그리디 알고리즘을 적용하는 것 같다.

나동빈님의 책에는 파이썬 코드로 작성되어 있으며, 저는 C++로 하나씩 문제를 해결하여 블로그에 올려볼 생각입니다.

알고리즘 초보분들 같이 문제들을 풀어보아요! 

int n, m, k, sum = 0; cin >> n>>m>>k; for (int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr, arr + n); for (int i = 0; i < m; i++) { if (i == 0) { sum += arr[n - 1]; } else if (i % k == 0) { sum += arr[n - 2]; } else { sum += arr[n - 1]; } } cout << sum;

핵심 코드부분은 입력받은 배열을 정렬 후, 반복문과 조건문을 이용하여 쉽게 해결할 수 있습니다.

---

수학적인 방법으로 접근을 해보면, 6+6+6+5 / 6+6+6+5 이런식으로 반복이 되는 것을 볼 수 있다.

배열의 n의 값이 늘어나게 되면 시간초과에러가 난다고 하는데, 시간초과가 날지는 모르겠네요.

아무튼 다시 코드를 짜보자면

int n, m, k, sum = 0; cin >> n>>m>>k; for (int i = 0; i < n; i++) { cin >> arr[i]; } sort(arr, arr + n); sum = arr[n - 1] * (m / (k + 1)) * k + arr[n - 2] * (m / (k + 1)); sum += (m % (k + 1)) * k * arr[n - 1]; cout << sum;