https://www.acmicpc.net/problem/15810 15810번: 풍선 공장 1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 www.acmicpc.net 풀이 간단하지만 타입에 조금 신경써야 하는 이분 탐색 문제. 걸리는 시간을 줄여가며 몇 개의 풍선이 만들어졌는 지 체크한다. 우선 반복문을 돌며 걸리는 시간 (mid) / 스태프의 풍선 제작 시간 (v[i]), 즉 스태프가 만든 풍선의 갯수를 cnt에 더해주었다. 그리고 cnt 가 만들어야하는 풍선의 갯수 (M)보다 많다면 true를 반환시켜서 걸리는 시간을 ..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 풀이 이해가 조금 어려웠던 문제. 돈이 남아도 다시 인출할 수 있기 때문에 큰 금액은 M 번에 맞춰 뽑을 수 있다. 그래서 돈이 모자랄 때 뽑는 경우를 M 과 비교하며 이분 탐색을 진행했다. is_possible 함수에 구현했는데 코드를 보면 이렇다. bool is_possible(int mid) { int cnt = 1; int tmp = mid; for (int i = 0; i < v.size();..

https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 문제가 짧아서 쉽게 접근했다가 틀렸습니다 폭탄 맞았던 이분 탐색 문제. 선분의 시작점과 끝점 각각 이분 탐색을 돌려주어야해서 함수로 만들어주었다. 그리고 점의 좌표를 입력받고 추가로 가장 끝 값을 더 넣어줘서 백터의 오버플로우를 방지했다. 예제의 1 3 10 20 30 값을 넣는다 했을 때, (오버플로우 방지용 1987654321) 2와 60이 들어온다면, 0 ~ ..

https://www.acmicpc.net/problem/1590 1590번: 캠프가는 영식 예제 1의 경우 150분, 200분, 250분, ..., 600분에 한 대씩 버스가 출발한다. 따라서 영식이는 300분에 버스를 타면 된다. www.acmicpc.net 풀이 처음에 모든 버스의 도착시간 배열을 만들까 하다가 입력 + 정렬 등등 코드가 너무 복잡해질 것 같아서 각 버스 별로 기다리는 최소 시간을 이분 탐색으로 찾아주었다. left = 첫번째 버스, right 는 마지막 버스로 입력 받고 is_possible 함수에서 시간 계산을 해주고 영식이가 도착한 시간 이후로 버스가 도착해야 탈 수 있기 때문에 T보다 큰 mid(버스)를 반환해주었다. 그리고 ret 에는 (mid 버스의 시간 - T) 의 계산..

https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 풀이 처음 입력받은 배열 A의 위치를 반환하지 않아도 돼서 편하게 풀 수 있는 이분 탐색 문제. map으로 구현해도 될 것 같지만 중복된 숫자가 있어서 이분 탐색이 편한 듯 하다. left 를 배열의 첫번째 인덱스인 0, right 를 마지막 인덱스로 설정하고 탐색을 진행했다. 구해야 하는 것이 처음으로 등장한 위치기 때문에 is_possible 함수를 D 가 더 작을 때 ..

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 풀이 전형적인 이분 탐색 문제. 는 모르겠고 이분 탐색 풀고 싶어서 풀어봤다. 이분 탐색 조건인 is_possible 함수 설정을 조금 생각해야했다. mid (가로등 높이) 값을 비교해야하는 부분이 1. 0 ~ 첫 가로등 2. 가로등 사이 3. 마지막 가로등 ~ N 이렇게 존재하는데 가로등 사이는 양 쪽에서 빛을 비추기 때문에 반으로 나눠주었다. 3가지 조건을 매번 탐색하며 진행했는데 쓰면서 보니 가..