나의개발일지

https://www.acmicpc.net/problem/2512 이 문제의 경우 예산액의 범위가 1 이상 100,000 이하여서 굳이 이분탐색이진 않아도 될 거 같긴 하다만, 이분탐색으로 풀었음.지방 예산액과 총 예산액이 주어졌을 때, 해당 총 예산액을 만족하는 최대 예산 상한액을 구하는 문제.그렇다면 이 최대 예산 상한액을 m으로 두고 1 ~ 최대 지방 예산액 사이에서 조건을 만족하는 m 값을 구하면 된다.조건을 만족하는 지 확인하는 코드는 다음과 같다. // 총 예산 계산int sum = 0;// 모든 지방의 예산의 예산 상한액보다 작을 경우 idx의 default값은 n이어야 함int idx = n;// 1. 현재 예산 상한액(m) 보다 작은 지방 예산의 합 = arr[i]원for(int i=0;..

https://www.acmicpc.net/problem/11561   처음에 이분탐색이라는 아이디어를 떠올리는 게 어려운 문제였다,,근데 자세히 보면 N의 범위로 보아 선형탐색은 절대 아니고, 두 번째 점프부터 이전 점프 + 1 긴 거리를 점프한다는 점에서 등차수열을 떠올릴 수 있다.그리고 최대 수이니 결국은 무조건 다음 식을 만족한다. => 다음 점프 = (이전 점프 + 1)그렇다면, 몇 개의 징검다리를 건넜을 때가 최대 징검다리가 될 까? 이 징검다리 수를 m으로 두고 이분탐색을 통해 조건을 만족하는 최대 m 값을 구하면 된다.그리고 조건은, m * (m + 1) / 2기 N의 값에 가장 가까우면 된다. (등차수열의 합 공식 사용)주의점은 N의 최대 범위를 고려하여 자료형을 long으로 사용해야 한..