[BOJ]15903: 카드 합체 놀이

chellchell·2020년 9월 5일
0

BOJ

목록 보기
1/6
post-thumbnail

문제

15903: 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.
두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력1

3 1
3 2 6

예제 출력1

16

예제 입력2

4 2
4 2 3 1

예제 출력2

19

풀이방법

먼저 배열에 입력된 값들을 (오름차순)정렬 한 후 첫 번째로 작은 값과 두 번째로 작은 값을 더하여 그 값들로 다시 첫 번째와 두 번째 값들을 덮어준다. 새로운 숫자가 또 입력됬으므로 다시 정렬해주고 덮어주는 작업을 반복해준다. 그리고 최종적으로 모든 카드의 값들을 합하여 반환한다.

코드

방법1 : C언어

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
long long* InPlaceSelectionSort(long long arr[], int n) {
	int i, j;
	for (i = 0; i < n - 1; i++) {
		int p = i;
		for (j = i + 1; j < n; j++) {
			if (arr[j] < arr[p]) {
				p = j;
			}
		}
		long long temp = arr[p];
		arr[p] = arr[i];
		arr[i] = temp;
	}
	long long x = arr[0], y = arr[1];
	long long sum = x + y;
	arr[0] = sum;
	arr[1] = sum;
	return arr;
}
long long card_sum(long long arr[], int m, int n) {
	long long sum = 0;
	for (int i = 0; i < m; i++) {
		arr = InPlaceSelectionSort(arr, n);
	}
	for (int i = 0; i < n; i++) {
		sum += arr[i];
	}
	return sum;
}
int main() {
	int n, m, i;
	long long arr[1001];
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}
	printf("%lld\n", card_sum(arr, m, n));
	return 0;
}

방법2 : C++언어

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int main() {
	int n, m;
	long long arr[1001];
	long long ret = 0;

	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
	}
	for (int j = 0; j < m; j++) {
		sort(arr, arr + n);
		long long tmp = arr[0] + arr[1];
		arr[0] = tmp;
		arr[1] = tmp;
	}
	for (int i = 0; i < n; i++) {
		ret += arr[i];
	}
	printf("%lld", ret);
}

후기

이 문제는 학교에서 배우는 선택정렬과 삽입정렬을 연습하기 위해 우선순위 큐 분류에서 문제를 찾다가 발견하게되었다. 내가 제시한 첫번째 코드로 하면 시간초과가 뜨긴하지만 나의 원래 취지는 선택정렬을 사용하고자 한것이므로 결과와 상관없이 개시는 해본다. 두번째 코드는 c++에서 sort함수를 사용하여 훨씬 빠르고 수월하게 정답이 나왔다.

profile
high hopes

0개의 댓글