주몽

후기

보자마자 2sum생각났었는데

가만생각하니까 다시 "조합"이랑 개념이 같음

순서 상관없이 2개 뽑아서 M을 만족하는거 뽑는거니까

그래서일단 bruteforce식으로 풀려다가 O(N^2)이 나오니까 pivot을 두개를 잡고 푸는 방식으로 할려다가 좀 돌고 돌아서 겨우 제출함.

일단 푸는 방법은

2sum

https://www.youtube.com/watch?v=OYQOe76Zc5I&t=126s

Brute-Force

강의 풀의와 같은데

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"

int N, M, C = 0;
int arr[150001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	cin >> M;
	
	for (int i = 0; i < N; ++i) cin >> arr[i];

	if (M > 200000) cout << 0 << endl;
	else
	{
		for (int i = 0; i < N; ++i)
		{
			for (int j = i + 1; j < N; ++j)
			{
				if (arr[i] + arr[j] == M) ++C;
			}
		}
	}
	
	cout << C << endl;

	return 0;
}

Pivot 2개 움직이기 (내가 푼 방법)

2sum영상에 착안해서 품.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl "\n"

int N, M, C = 0;
vector<int> vec;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	cin >> M;
	vec.resize(N);
	
	for (int i = 0; i < N; ++i)
	{
		cin >> vec[i];
	}

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

	int l = 0;
	int r = vec.size() - 1;

	while (l != vec.size() - 1)
	{
		if (vec[l] + vec[r] == M)
		{
			++C; ++l; r = vec.size() - 1;
		}
		else --r;

		if (l == r)
		{
			++l;
			r = vec.size() - 1;
		}
	}

	if (vec.size() == 1 && vec[0] == M)
	{
		cout << 1 << endl;
		return 0;
	}
	
	cout << C << endl;

	return 0;
}

좀 더럽긴한데 일단 이런식으로 풀었다.

중요한 부분 ❗❗❗

문제에서 보면은 아래가 조건이라

고유한 번호는 100,000보다 작거나 같은 자연수이다.

두개를 조합해서 만드는 것이니까

if (M > 200000) cout << 0 << endl;

위의 분기문이 들어갔던 것이다.

고유 번호 최대 10만이니까 두개 더하면 20만인데

20만을 넘는 조건을 채울 수 없음 ㅇㅋ?