이분탐색2 [백준] 2295번 세 수의 합 (C++) https://www.acmicpc.net/problem/2295 이 문제는 집합에 대한 수가 입력으로 주어졌을때 임의의 수 x, y, z를 더했을때 집합에 있는 K가 되는 수중 가장 큰 수를 구해야 하는 문제이다. 처음엔 모든 경우의 수를 구해서 거기서 집합에 있는지 탐색을 하려했는데 메모리 초과가 나서 다른 방법을 생각을 해봤다먼저 식을 세웠는데 x + y + z = K이다.결국 x + y = K - z 이기 때문에 이걸 통해서 가장 큰 집합 K를 구할 수 있다고 생각을 했다. 정답 코드#include using namespace std;typedef pair pii;typedef long long ll;#define endl "\n"#define MAX 1e9int dx[] = {0, 1, -1.. 2025. 7. 18. [백준] 1800번 인터넷 설치 (C++) https://www.acmicpc.net/problem/1800 문제를 보고 다익스트라 알고리즘을 사용해야 하는것은 알겠으나여기서 1번노드 부터 N번 노드까지 확장했을때 최단경로를 구하는 것은 아니였기에 어떤 방법을 사용해서 최소 값을 출력해야하는지 구할 수가 없었다.따라서 다른 사람들 풀이를 보니 이분탐색을 활용하여 간선에 대한 상한선을 지정해 준다 즉 비용이 mid 이하인 간선을 무료로 사용하고이보다 큰 간선은 비용이 든다고 가정했을 때, 총 유료 간선의 개수가 K개 이하로 N번노드에 도달할 수 있는지 판별하는 방법이다. 예를들어 다음 테스트 케이스 1번을 보자 이분탐색을 사용해서 mid 값을 4라고 지정했을때 3번 노드 2번 노드의 누적 거리 값은 0으로 될 것이다.하지만 4번 노드 5번 노드는.. 2025. 6. 26. 이전 1 다음
