백준 BOJ 1940 - 주몽

베이직한 투 포인터

www.acmicpc.net/problem/1940

1940번: 주몽

번호를 정렬한 뒤

가장 앞 값과 가장 뒷 값의 인덱스를 변수로 잡는다

만약 더했을때 m과 같다면, 갑옷을 만드는데 사용하므로

앞값++, 뒷값--를 동시에 해주고

m보다 크다면 뒷값이 너무 큰 경우이므로 뒷값--만,

m보다 작다면 앞값이 너무 작은 경우이므로 앞값++만 해주면

O(N)정도에 끝낼수 있다.

 

#include <stdio.h>
#include <algorithm>

using namespace std;

int arr[23456] = {0};

int main(){
	int n,m;
	int s,e;
	int ans = 0;
	scanf("%d %d", &n, &m);
	for(int i=0; i<n; i++) scanf("%d", &arr[i]);
	
	s = 0;
	e = n-1;
	
	sort(arr, arr+n);
	
	while(s<e){
		if(arr[s]+arr[e] == m){ ans++; e--; s++; }
		if(arr[s]+arr[e] >  m) e--;
		if(arr[s]+arr[e] <  m) s++;
	}
	printf("%d", ans);
	return 0;
}