문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 간단한 이분탐색 문제 같지만 생각할 예외가 있는 문제였습니다. 처음에는 단순히 배열을 정렬한 후 초기 start를 0, end를 현재 확인하고 있는 인덱스의 앞까지로 해서 이분탐색을 진행하면 되지 않을까 했습니다. 하지만 이렇게 할 경우 아래 테케와 같이 동일한 숫자가 여러 개일 경우 문제가 발생합니다. 4 0 0 0 0 1번 0은 뒤에 있는 0들을 더해서 만들 수 있는 숫자임에도 인덱스 범위로 인해 만..
이분탐색
문제 링크 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 문제 풀이 이분 탐색으로 푸는 문제이다. 시작점을 1, 끝점을 입력받은 len의 최댓값으로 두고 mid를 구하여 len에서 뺀 값을 모두 더하는 것으로 상근이가 얻을 수 있는 길이를 구한다. 이 때, 주의해야 할 점은 나무의 길이가 중간값보다 길 때만 빼야한다는 것이다. 이 조건문을 빼놓으면 마이너스 값도 얻을 수 있는 값을 더할 때 포함되므..
문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 문제 풀이 이분 탐색으로 풀이를 하면 되는 문제이다. 길이를 기준으로 랜선의 개수를 결과내면 된다. 1을 시작값, 입력받은 길이 중 최댓값을 마지막값으로 하여 중간값을 정하고 해당 중간값으로 길이를 나누어 나온 개수를 합쳐 해당 개수가 요구받은 N값보다 작을 경우 중간값을 줄이기 위해 end 값을 mid - 1로, N값보다 클 경우 중간값을 늘리기 위해..
