Smallsoft

문제링크문제 유형은 약간의 수학과 이진탐색에 관한 문제이다. 문제의 조건에 충족하면서 최대의 징검다리를 밟기 위해서는1부터 1씩 늘어나는 수열 1, 2, 3 ... k 즉 각 항의 차이가 1인 등차수열을 합을 구하면 되는 문제이다. 등차수열의 합 S = (k * (k + 1)) / 2 를 구한뒤 이 수가 N(징검다리의 수)보다 작은지를 확인하면되는데문제는 N이 10^16 이므로 k를 1부터 구한다면 시간초과가 날것이다. 여기서 이진탐색을 적용해 k를 구하면 문제가 해결된다.소스코드는 다음과 같다.#include using namespace std;/*마지막 징검다리는 꼭 밟아야한다.첫번째는 아무곳이나 밟을수있고두번째 점프부터는 이전 점프거리보다 1 이상 더 뛰어야한다.가장 많이 밟고 가고싶어한다.즉 n번..

문제 링크이 문제는 여태까지의 게임횟수와 이긴횟수를 주고 이후 계속 승리한다고 가정하였을때 승률이 바뀌는 지점은 언제인지를 묻는 문제이다. 최대 10억을 주기 때문에 1씩 올려서 승률이 바뀔때를 체크한다면 시간초과로 이어진다. 특히 승률이 98.0 에서 99로 올릴때 가장 많은 연산이 들어간다.예시: x의 최대값 10억이 들어오고 y는 98프로에 맞는 980,000,000일 경우 99퍼로 올리기위해서는 1억번의 연산이 필요하다.이렇게 큰범위를 탐색해야할때 자주 쓰는게 있으니 이진탐색이다.범위를 반으로 나눠 체크하니 연산횟수를 줄여 2초안에 충분히 가능해보인다.수도코드초기 입력 처리• 총 게임 수(x)와 이긴 게임 수(y)를 입력받는다.• 초기 승률을 계산한다.예외 처리• 만약 초기 승률이 99% 이상이면..