본문 바로가기

이분탐색5

[랜덤] BOJ 1011 - Fly me to the Alpha Centauri (C++) 문제 링크백준 1011풀이 시간아이디어: 20분코딩: 10분문제 풀이조건)처음과 끝 직전에는 무조건 속도 1로 도달해야한다.K번째 턴의 속도 V[K]는 V[K-1]-1, V[K-1], V[K-1]+1조건을 해결하기 전 먼저 어떤 규칙이 있을 것 같다고 생각했다.예를 들어 A=0, B=10이라고 가정하자.구간의 길이는 총 B-A = 10이다.눈으로 계산해보면0 -(+1)-> 1, 1 -(+2)-> 3, 3 -(+3)-> 6, 6 -(+2)-> 8, 8 -(+1)-> 9, 9 -(+1)-> 10 이다.가운데 값을 기준으로 양쪽으로 내려가는 것을 볼 수 있다.무엇보다 끝에 +1이 두번 나오는 것을 통해, 남는 거리만큼 +1을 하면 될 것 같다고 생각했다.이를 표로 남겨보자왼쪽 칼럼을 속도라고 했을 때 개수.. 2024. 10. 20.
BOJ 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 접근휴게소 간 거리가 최소가 되는 거리를 찾는 문제이다.최소 거리를 찾는 문제이므로 매개변수 탐색을 통해 해결할 수 있다. 무엇을 기준으로 이분적으로 구분을 하면될까?휴게소 사이 (+ 시작지점과 끝지점 포함)에 새로운 휴게소를 건설한다는 가정하에 N의 거리를 두고 새로운 휴게소가 지어진다고 가정해보자.이렇게 되면 우리는 휴게소 사이에 둘 새로운 휴게소를 두는 지점을 이분적으로 탐색하면 된다. 예제 1번을 예를 들면휴게소 사이에서 어떤 거리 D을 기준으로 새로운 휴게소가 세워진다. 만약 휴게소 사이를 D으로 나누었을 때, 새롭게 세워진 휴게소가 M개가 넘는다면D를 늘려야 하므로 left = mid+1을 하면 된다. 반대로 새롭게 세워진 휴게.. 2024. 7. 12.
BOJ 3151 - 합이 0 3151번: 합이 0 (acmicpc.net) 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 접근 방법 3개의 수의 합이 0이 되는 조합을 모두 찾는 문제이다. 2문제를 미리 다 더한 후, 마지막 하나를 이분탐색으로 구하는 문제이다. 이 문제를 처음할 때 실수한 부분이 중복되는 값을 고려하지 않은것이다. 만약, 8 -10 5 5 5 5 5 5 5 다음 케이스가 올 경우, 5를 모두 개별 취급을 해야하므로 21이 되어야 한다. 그러나, 이분탐색의 경우 중복을 처리하는게 쉽지 않기 때문에 lower_bound와 up.. 2024. 4. 17.
BOJ 2295 - 세 수의 합 2295번: 세 수의 합 (acmicpc.net) 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 접근 방법 백트래킹, 브루트포스말고는 어떻게 풀어야할지 감이 안잡혔다. 그래서 결국 알고리즘 분류를 봤다... 이 문제에서 어떻게하면 이분탐색으로 풀수있을까 많이 생각해보았다. 무엇을 기준으로 대소비교를 할 것인가? 처음엔 원소의 인덱스를 기준으로 생각해보려고 했지만, 해당 원소의 더한 값을 구하려면 이전 원소들을 모두 3개씩 더해야 한다. 그리고 무엇을 기준으로 .. 2024. 4. 13.
BOJ 16401 - 과자 나눠주기 16401번: 과자 나눠주기 (acmicpc.net) 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 접근 방법 가장 길게 과자를 N명에게 나눠주는 문제이다. 이때 핵심이 과자를 부러뜨리면 다시 합칠 수 없다는 것이다. 예제 1을 보자. 1 2 3 4 5 6 7 8 9 10에서 3명에게 가장 긴 과자를 주려면 8 , 9 , 10을 선택하여 9와 10을 각각 1, 2 만큼 부러뜨려 8로 맞춰 주면된다. 예제 2번의 경우 한 번더.. 2024. 4. 13.

티스토리툴바