Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- swea
- dp
- 응용 계층
- BHS
- leetcode
- 관계형 모델
- boot sequence
- Djikstra
- Application Layer
- Transport layer
- 데이터베이스
- BST
- 문제풀이
- Database
- 백준
- 자료구조
- Embedded
- 다익스트라
- 네트워크
- 프로그래머스
- 임베디드
- 부트시퀀스
- baekjoon
- ps
- STL
- Network
- DB
- C++
- 릿코드
- 전송 계층
Archives
- Today
- Total
BOBO's Note
[ Baekjoon ] 1920. 수 찾기 본문
https://www.acmicpc.net/problem/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);
}
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ Baekjoon ] 17406. 배열 돌리기 4 (0) | 2020.06.02 |
---|---|
[ Baekjoon ] 17070. 파이프 옮기기 1 (0) | 2020.06.02 |
[ Baekjoon ] 17837. 새로운 게임2 (0) | 2020.05.31 |
[ Baekjoon ] 5373. 큐빙 (0) | 2020.05.31 |
[ Baekjoon ] 10217. KCM Travel (0) | 2020.05.28 |
Comments