728x90
오늘은 이진탐색으로 풀 수 있는 문제를 가져왔다.
문제 1789번
https://www.acmicpc.net/problem/1789
이진탐색을 하려면 정렬은 필수인데 여기서는 정렬된 자연수를 생각하므로 따로 정렬은 필요없다.
start와 end를 각각 1과 S로 잡고 그 사이의 값을 mid로 잡는다. while문을 이용하여 start<=end일때까지 계속 반복해준다. 1부터 mid까지의 숫자들을 모두 더했을 때 S보다 작거나 같으면 result에 해당 숫자들 중 가장 큰 mid를 넣어주고 start에는 mid+1을 넣어준다. 만약 반대의 경우라면 범위를 작게 만들 필요가 있기 때문에 end에 mid-1을 넣어준다.
#include <iostream>
using namespace std;
int main() {
long S;
cin >> S;
long start = 1;
long end = S;
long result=0;
while (start <= end) {
long mid = (start + end) / 2;
if ((mid + 1)*mid / 2 <= S) {
result = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
cout << result;
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 27866번 - 문자와 문자열 (0) | 2024.03.27 |
---|---|
[C++] 백준 1072번 - 게임 (0) | 2024.03.27 |
[C++] 백준 10871번 - X보다 작은 수 (0) | 2024.03.24 |
[C++] 백준 10773번 - 제로 (2) | 2024.03.24 |
[C++] 백준 4963번 - 섬의 개수 (2) | 2024.03.22 |