알고리즘 :: 백준 :: 1940 - 주몽

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력

• 재료개수: 1 ≤ N ≤ 15,000
• 갑옷 1개 만드는 데 필요한 수: 1 ≤ M ≤ 10,000,000
• A[i] ≤ 100,000, 중복없음

출력: 갑옷을 만들 수 있는 개수

 

✏️ 문제풀이

• 중복된 번호는 없기 때문에 A + B = M이 성립하는 재료 A, B를 발견하면 바로 선택하면 됩니다.
  (임의의 재료를 어느 재료와 조합하냐에 따라 만들 수 있는 갑옷 개수가 달라지거나 그렇지 않기 때문입니다.)
• 하지만, 모든 경우의 수를 탐색하려면 $O(N^2)$이 소요되는데, N이 최대 15,000이므로 시간제한 2초내에 풀 수 없습니다.
  (사실 이 문제는 이렇게 풀어도 통과는 됩니다)
• 더 효과적으로 탐색하려면, 투포인터를 사용하면 됩니다.
  • 재료 번호를 저장한 배열을 정렬한다.
  • 맨 왼쪽과 맨 오른쪽 인덱스를 가리키는 변수(커서)를 2개 만든 뒤
  • 두 커서가 가리키는 재료 번호의 합이
    • M보다 크면, 오른쪽 커서를 한 칸 낮춰야 합니다.
    • M보다 작으면, 왼쪽 커서를 한 칸 높여야 합니다.
    • M과 같으면, 조합을 찾은것이니 결괏값 + 1하고, 왼쪽 커서 증가, 오른쪽 커서 감소합니다.

놓치기기 쉬운 점

재료번호는 최대 100,000이기 때문에 입력받은 값 M이 200,000 이상이면 절대로 만들 수 없습니다.

• 이 문제는 다행히 그 점까지는 고려하지 않아도 정답이 나옵니다.
• 하지만, M이 200,000 이상인 경우에 대한 쿼리가 있다면, 쓸데없이 계속 위의 O(NlogN) 정렬과 O(N) 탐색을 계속 해야 할 것입니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

int N, M, result;
array<int, 15001> arr;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) cin >> arr[i];
	if (M < 200'000) {
		// Before use two pointer, we should sort array first.
		sort(begin(arr), begin(arr) + N);
		
		int l = 0, r = N - 1;
		// Two pointer begins
		while (l < r) {
			int sum = arr[l] + arr[r];
			if (sum < M) l++;
			else if (sum > M) r--;
			else { l++, r--, result++; }
		}
	}
	cout << result;
}

 

🔗 코드 링크

🕧 결과