[ Baekjoon ] 1920. 수 찾기

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

1920번: 수 찾기

풀이 방법

주어진 시간 내에 답을 찾기 위해서는 이진 탐색에 DP를 사용해 풀어야 한다. 그리고 std::cin/std::cout 보다는 scanf()/printf()를 사용해야 한다.

 

찾으려는 수를 key로, 존재 여부를 value로 갖는 unordered_map memo를 선언한다. 그 후, 탐색을 하기 전에 memo를 먼저 살펴봐 데이터가 없는 경우에만 실제 이진 탐색을 실행한다. 그리고 그 결과를 memo에 업데이트한다.

unordered_map<int, bool> memo;

for(int i=0; i<M; i++){
	scanf("%d", &x);
	auto itr = memo.find(x);
	if(itr == memo.end()){
		ret = binary_search(v, x);
		memo.insert({x, ret});
	}
	else{
		ret = itr->second;
	}
	printf("%d\n", ret);
}

전체 코드는 여기서 확인할 수 있다.