본문 바로가기
반응형

이분탐색3

[백준 2295] 세 수의 합 문제 출처 : https://www.acmicpc.net/problem/2295 집합에 포함된 세 수를 더한 결과가 집합 내에 있는 가장 큰 수가 되는 경우를 찾는 문제 입니다. 세 수 x, y, z와 그 결과로 가장 큰 수 k를 찾아야 합니다. 이 때 꼭 기억해야 하는 부분은 x, y, z, k의 값이 서로 같아도 된다는 부분 입니다. 저는 세 수가 같을수는 없다고 생각하고 아무리 풀어도 틀리다고 나와 문제를 다시 제대로 읽어보니 숫자가 중복되어도 상관 없다는 부분을 찾을 수 있었습니다. 저와 같은 실수를 하지 마시기 바랍니다.아이디어세 개의 수를 더하기 때문에 시간복잡도가 높을 것으로 생각이 듭니다. 하지만 조금만 더 생각해보면 시간복잡도를 줄일 수 있는 아이디어가 있습니다. 우리가 구해야 하는 공식.. 2024. 5. 2.
[백준 2512] 예산 문제 출처 : https://www.acmicpc.net/problem/2512 렌선 자르기 문제와 비슷한 느낌이 드는 문제 입니다. 다빈치코딩 알고리즘에 넣기에는 중복적인 내용이라 블로그에 추가하였습니다.문제 이해하기예산이 낮은곳은 그대로 두고, 예산이 높은곳만 줄여나가며 총액보다 작게 만드는 문제 입니다.이 문제는 일반적인 이분 탐색 문제와 다른점이 있습니다. 바로 예산을 증액할 필요는 없다는 것입니다. 예산의 총액이 신청한 예산보다 크다면 더이상 예산을 늘릴 필요 없이 최대값을 출력하면 됩니다. 이 부분만 주의하면 문제를 해결할 수 있습니다.코드 작성그럼 코드를 작성하며 문제를 해결해 보겠습니다.입력 받기N = int(input())arr = list(map(int, input().split())).. 2024. 5. 1.
[백준 28216] 2023 정올 초등부 1차 아이템 획득 문제 출처 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 이 문제는 2023년도 정보 올림피아드 1차 초등부 3번 문제로 출제 되었던 문제 입니다. 문제 이해하기 2차원 지도에서 아이템을 모으는 문제로 인접 행렬로 구현하면 될 것 같은 문제 입니다. 하지만 지도의 크기가 20만 입니다. 또한 이동하는 횟수인 Q 역시 20만 입니다. 쉽게 시간복잡도가 20만 * 20만이라는 것을 알 수 있고 시간초과가 예상되기 때문에 인접 행렬로 문제.. 2024. 1. 30.
반응형

티스토리툴바