[C++] 백준 15903번 카드 합체 놀이

1. 문제이해

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

15903번: 카드 합체 놀이

 

 

아기 석환이는 n장의 카드를 가지고 카드 합체 놀이를 하려고 한다.

카드 합체 놀이의 과정은 아래와 같다.

 

1. x번 카드와 y번 카드를 골라 그 두장에 쓰여진 수를 더한 값을 계산한다.

2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어쓴다.

 

카드합체를 총 m번 할 때, n장의 카드에 적혀있는 수를 모두 더한 값이 점수가 된다.

이때, 만들 수 있는 가장 작은 점수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

위와 같은 규칙에 따라 m번 카드 합체를 진행, 카드의 총합을 가장 적게 만드는 것이 목표이다.

카드의 총합을 가장 적게 만드려면, 다시 말해, 가장 작은 숫자끼리 합체하면 된다.

 

 

예제 입력 1을 보자.

3 2 6이 적힌 카드 3장을 1번 카드합체 해야한다.

작은 숫자 순서대로 정렬하면, 2 3 6

가장 작은 숫자끼리 카드합체 해야, 합칠 수 있는 수들 중 가장 작은 숫자가 나오므로,

여기서 가장 작은 숫자끼리 합체하면, 2 + 3 = 5 로 두 장의 카드를 모두 덮어 쓰게 된다.

따라서, 5 5 6 이 1번의 카드합체를 끝낸 결과이며,

5 + 5 + 6 = 16이 만들 수 있는 가장 작은 점수가 된다.

 

예제 입력 2도 살펴보자.

4 2 3 1이 적힌 카드 4장을 2번 카드합체 해야한다.

작은 숫자 순서대로 정렬하면, 1 2 3 4.

여기서 가장 작은 숫자끼리 합체하면, 1 + 2 = 3 로 두 장의 카드를 모두 덮어 쓰게 된다.

따라서, 3 3 3 4 가 1번의 카드 합체를 끝낸 결과이다.

다시 가장 작은 숫자끼리 합체하면, 3 + 3 = 6 로 두 장의 카드를 모두 덮어 쓰게 된다.

따라서, 6 6 3 4 가 2번의 카드합체를 끝낸 결과이며,

6 + 6 + 3 + 4 = 19가 만들 수 있는 가장 작은 점수가 된다.

 

 

위 두 가지 예제 입력 풀이 방식을 통해 알 수 있는 풀이법은 다음과 같으며,

해당 풀이법을 통해 도출해낸 코드는 아래와 같다.

 

1. 카드의 숫자들을 작은 순서대로 정렬한다.

 

2. 가장 작은 숫자 2개를 합체, 합으로 덮어쓴다.

(단, 가장 작은 숫자 2개는 정렬했으므로, 무조건 앞 2개의 카드에 해당)

 

3. 위 과정을 m(주어진 카드합체 횟수)번 반복한다.

 

 

 

3. 소스코드

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

int main() {
	int n;                 // 카드의 개수
	int m;                 // 카드 합체를 몇번 하는지

	// 아래 변수들은 값의 범위가 크기 때문에, long long 형 필요
	long long card[1000];  // 카드의 숫자
	long long sum;         // 카드 두 장을 골라 합한 값
	long long min_sum = 0; // 만들 수 있는 가장 작은 점수

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}

	// 오름차순 정렬
	sort(card, card + n);

	// 카드 합체
	for (int i = 0; i < m; i++) {
		sum = card[0] + card[1];
		card[0] = sum;
		card[1] = sum;
		sort(card, card + n);
	}

	for (int i = 0; i < n; i++) {
		min_sum += card[i];
	}

	cout << min_sum;

	return 0;
}

카드의 개수(N), 카드 합체 횟수(M)를 입력받는다.

그리고, 각 카드에 적힌 숫자(card), 숫자를 합한 값(sum),

카드 합체를 통해 만들 수 있는 가장 작은 수(min_sum)는 모두 long long 형으로 선언해주었다.

(int 형으로 선언해주면, 큰 값의 합이 들어간 경우 범위를 벗어나 오류가 나게 된다.)

 

각 카드에 적힌 숫자를 모두 입력받고 오름차순으로 정렬 후, for문을 통해 카드합체를 시작한다.

카드 합체는 2. 문제풀이 과정에서 도출한 방법으로 구현했다.

오름차순으로 정렬된 카드의 숫자 중 가장 작은 두 숫자는 무조건 앞 2장의 카드가 되므로,

앞 2장의 카드(card[0], card[1])를 합체, 합체한 값을 덮어쓴다.

이후 다시 오름차순으로 정렬 후, 같은 과정을 반복하며 다시 가장 작은 카드 2장을 m번 합체 한다.

 

m번 카드 합체를 한 후, 각 카드의 숫자를 모두 합한 값이

카드합체를 통해 만들 수 있는 가장 작은 수(min_sum)가 된다.

 

 

---

문제에 대한 지적이나 질문은 언제나 감사하게 받고 있습니다.😊