본문 바로가기

알고리즘2

백준 2467 - 용액 (이분탐색, 투포인터) 더보기 https://www.acmicpc.net/problem/2467 👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다. 문제 요약 - 산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어진다. - 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가까운 용액을 만들어 내는 두 용액을 출력하라. * 혼합한 용액의 특성값: 혼합에 사용된 각 용액의 특성값의 합 제한 조건 - 전체 용액의 수 (2≤ N ≤ 100,000) (100,000 가지 중 2가지 경우의 수를 찾으면 경우의 수가 상당히 많아져 1초만에 문제를 풀기에 무리가 있다.) - 용액의 특성 값 (-1,000,000,000 ≤ M ≤ 1,000,000,000) (Long 타입) 아이디어 - Two pointer (왼쪽 인덱스.. 2022. 4. 18.

백준 1477 - 휴게소 세우기 더보기 https://www.acmicpc.net/problem/1477 👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다. 문제 요약 - 다솜이는 현재 고속도로에 N 개의 휴게소를 가지고 있다. - 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. - 이미 휴게소가 있는 곳에는 휴게소를 세울 수 없다. - 휴게소는 정수 위치에만 세울 수 있다. Q. 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값의 최소를 구한다. ex. {200, 701, 800} 이 있을 때, 휴게소가 없는 구간의 길이는 {501, 101}이다. 이 중 최댓값을 501이다. 만약 휴게소를 1(M)개 더 지으려고 할 때, 이미 휴게소가 세워지지 않았다면 많은 후보가 생긴다. 451 에 세운다.. 2022. 4. 16.

이전 1 다음

티스토리툴바