본문 바로가기

Beakjoon/binary search

 (7)
[백준] 7795번 먹을 것인가 먹힐 것인가 (C++) - binary search 문제 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 코드 #include #include using namespace std; int a[20000]; int b[20000]; int main(){ int t,n,m; cin >> t; while(t--){ cin >> n >> m; for(int i=0; i> a[i]; } for(int i=0; i> b[i]; } sort(a,a+n); ..
[백준] 1072번 게임 (C++) - binary search 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 코드 #include using namespace std; int main(){ long long x,y; cin >> x >> y; long long z=100*y/x; long long start=0; long long end=x; long long result=-1; while(startz){ result=mid; end=mid-1; }else{ start=mid+1; } } c..
[백준] 2512번 예산 (C++) - binary search 문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 코드 #include #include #include using namespace std; vector v; int n, a; long long handleSum(int cri){ long long sum_val=0; for(int i=0; icri) sum_val+=cri; else sum_val+=v[i]; } return sum_val; } int main(){ cin >> n; ..
[백준] 1764번 듣보잡 (C++) - binary search, map 문제 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 코드 binary search 풀이 #include #include #include using namespace std; int main(){ int n, m; cin >> n >> m; vector nh; vector nhs; for(int i=0; i> a; nh.push_back(a); } sort(nh.begin(), nh.end()); for(int i=0; i> b; int st..
[백준] 1654번 랜선 자르기 (C++) - binary search 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 코드 #include #include using namespace std; int main(){ int k, n; cin >> k >> n; int max = 0; vector v; for(int i=0; i> a; v.push_back(a); if(a > max){ max = a; } } long long start = 1; long long end = max;..
[백준] 2805번 나무 자르기 (C++) - binary search 문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 코드 잘못된 코드 #include #include using namespace std; int main(){ int n, m; cin >> n >> m; vector trees; int max = 0; for(int i=0; i> th; trees.push_back(th); if(max < th){ max = th; } } int start = 0; i..
[백준] 1920번 수 찾기 (C++) - binary search 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 첫번째 시도 #include #include using namespace std; int main(){ int n, m, a; vector v; bool flag; cin >> n; for(int i=0; i> a; v.push_back(a); } cin >> m; for(int i=0; i> a; for(int j=0; j a; whil..

티스토리툴바