[백준] 1940 주몽 - C++

문제) 주몽은 철기군을 양성하기 위해 야철 대장에게 철기군이 입을 갑옷을 만들라고 명했다. 갑옷을 만드는 재료는 고유한 번호가 있고 갑옷은 2개의 재료로 만드는 데 2가지 재료를 합쳐 M이 되면 갑옷이 만들어진다. 가지고 있는 재료로 몇 개의 갑옷을 만들 수 있는 지 구하는 프로그램을 만들어보자.

    첫째 줄엔 재료의 개수 n, 둘째 줄엔 갑옷을 만드는데 필요한 수 m, 마지막 n개의 재료들이 공백을 두고 주어진다.

    시간제한은 2초, 메모리 제한은 128MB이다.

 

값을 정렬한 다음 투포인터를 이용해 풀면 쉬워지는 문제다.

 

i가 j보다 작을 때까지
    i번째 수와 j번째 수의 합이 m과 일치하다면
        cnt 값을 올리고 i는 +, j는 -시키기
    i번째 수와 j번째 수의 합이 m보다 작다면
        i값을 올리기
    크다면
        j값을 내리기

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	vector<int> vec(n, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> vec[i];
	}

	sort(vec.begin(), vec.end());

	int i = 0, j = vec.size() - 1;
	int cnt = 0;
	while (i < j)
	{
		if (vec[i] + vec[j] == m)
		{
			i++;
			j--;
			cnt++;
		}
		else if (vec[i] + vec[j] < m)
		{
			i++;
		}
		else
		{
			j--;
		}
	}

	cout << cnt;

	return 0;
}