백준 1940 주몽 C/C++

주몽 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

11342

5416

4185

47.299%

문제

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

예제 입력 1 복사

6
9
2 7 4 1 5 3

예제 출력 1 복사

2

#include <iostream>


using namespace std;

void MergeTwoArea(int arr[], int left, int mid, int right);
void MergeSort(int arr[], int left, int right);


int arr[15001];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, pos1, pos2, cnt = 0;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	MergeSort(arr, 0, n - 1);

	pos1 = 0;
	pos2 = n - 1;
	
	while (pos1 < pos2)
	{
		if (m > (arr[pos1] + arr[pos2]))
		{
			pos1++;
		}
		else if (m < (arr[pos1] + arr[pos2]))
		{
			pos2--;
		}
		else
		{
			cnt++;
			pos1++;
			pos2--;
		}
	}

	printf("%d", cnt);
	return 0;
}

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

 

 

n개의 숫자를 받아, 그중에 2개의 합이 m이 되는 것을 고르면 된다.

 

예제에서는

6

9

2 7 4 1 5 3

의 입력을 받는다.

 

여기서 2+7, 5+4를 하면 9가 되고, 2가지가 된다.

 

 

이를 쉽게 풀기 위해 오름차순으로 정렬한다.

정렬이 n^2이 되지 않게, nlog n의 병합정렬로 정리를 했다.

 

 

이후에, pos1은 맨 왼쪽, pos2는 맨 오른쪽에 위치한다.

 

맨 처음 1+7을 더한다. 그러면 8이고 9보다 작다. pos1을 오른쪽으로 옮긴다.

그럼 2+7 =9 가 된다.

원하는 값을 찾았으니 cnt++해주고, pos1과 pos2를 각각 옮겨준다.

왜냐하면 pos1만 옮겨봐야 값은 9를 넘어가고, pos2만 옮기면 반드시 9보다 작아진다.

 

 

이러면 3+5가 된다.

이런 형태를 계속 반복한다.

 

이를 정리하면 다음과 같다.

 

1) arr[pos1] + arr[pos2] >M : pos2--

2) arr[pos1] + arr[pos2] <m : pos1++

3) arr[pos1] + arr[pos2] ==m: pos1++, pos2--, cnt++;

 

이 된다.