백준 1940번 주몽

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

 

아이디어:

1. vector 사용

2. 입력받은 vector에서 합이 되는 두 수 찾기

3. 이중반복문으로 순회

 

// 1940

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

using namespace std;

int main() {

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

	long N, M, answer = 0;
	cin >> N >> M;
	vector<long> A(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (A[i] + A[j] == M)
				answer++;
		}
	}

	cout << answer;

	return 0;

}

 

모범답안:

1. 정렬 후 투 포인터 사용해서 시간복잡도 최적화 (84ms > 4ms)

2. algorithm의 sort 함수에서 vector의 시작점, 끝점 사용

sort(A.begin(), A.end())

 

// 1940

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

using namespace std;

int main() {

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

	long N, M, answer = 0;
	cin >> N >> M;
	vector<long> A(N, 0);
	long start = 0;
	long end = N - 1;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

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

	while (start < end) {
		if (A[start] + A[end] == M) {
			answer++;
			start++;
		}
		else if (A[start] + A[end] < M) {
			start++;
		}
		else if (A[start] + A[end] > M) {
			end--;
		}
	}

	cout << answer;

	return 0;

}