[이것이 코딩테스트다]큰 수의 법칙(C++)

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118 

이것이 취업을 위한 코딩 테스트다 with 파이썬

해당 도서의 Part 02. 그리디 알고리즘 에서 큰 수의 법칙 문제를 풀이한다.

 

문제 조건: N개의 숫자를 입력받은 뒤 M번의 덧셈을 통해 가장 큰 수를 만들어낸다. 한 숫자는 K번 연속해서 더해질 수 있으며, 숫자가 같지만 인덱스가 다른 경우 다른 요소로 취급한다.

 

ex) N=5, M=7, K=2 고 3 4 3 4 3 입력받았을 경우, 4+4+4+4+4+4+4 가능하다.

ex) N=5, M=8, K=3 고 2 4 5 4 6 입력받았을 경우, 6+6+6+5+6+6+6 가능하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

int N, M, K;
int* arr;

void input();
bool compare(int i, int j);
void sortArr();
void answer();

int main() {
	scanf("%d %d %d", &N, &M, &K);

	input();
	sortArr();
	answer();

}

void input() {
	arr = new int[N];
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	return;
}

bool compare(int i, int j) {
	return i > j;
}

void sortArr() {
	sort(arr, arr+N, compare);
	return;
}

void answer() {
	int limit = 0, index = 0;
	int result = 0;

	while (limit < M) {
		for (int i = 0; i < K; i++) {
			result += arr[index];
			limit += 1;
			if (limit == M) break;
		}

		if (limit == M) break;
		else {
			result += arr[index + 1];
			limit += 1;
		}
	}
	printf("%d", result);
}

• input(): 입력함수
• compare(): sort함수의 기준을 정해주는 함수
• sortArr(): sort 이용하여 배열 정렬
• answer(): 문제 풀이 함수

---

솔루션 도출 과정

1) 한 수는 K번 연속 더해질 수 있으며, 총 M회의 숫자가 더해져야 한다.

2) 입력받은 숫자들을 배열로 만들어 정렬하면 제일 첫번째 요소는 무조건 가장 큰 수가 된다.

3) 첫번째 요소를 연속해서 M번 더할 수는 없지만, K번 더한 다음 중간에 다른 요소를 한 번 더해주면 다시 K번 연속해서 더할 수 있다.

4) 중간에 다른 요소를 더해줄 때는 두번째 요소를 더하면 된다. 이 배열은 내림차순 정렬되어있으므로 두번째 요소가 첫번째 요소를 제외하고 이 배열에서 가장 큰 수이기 때문이다.