백준 23978번 급상승

문제 설명

이번 문제는 효석이가 자신이 정한 N개의 날짜에 코인을 X원으로 급상승시키고 처음 코인 가격이 오른 날부터 한 개씩 매도할 때, K원 이상 현금화할 수 있는 가장 작은 정수 X를 구하는 문제입니다.

(단, 코인이 X원으로 오른 뒤 하루에 1원씩 0원이 될 때까지 가격이 낮아진다.)

 

문제 풀이

아이디어

X를 알 때 최종 현금화할 수 있는 금액을 구하는 방법

정해진 N개의 날짜에 코인이 X원 상승한 뒤, 하루에 1원씩 작아집니다.

여기서, 코인이 급상승하는 날짜 사이의 일 수가 X보다 크다면 코인은 0원까지 떨어지게 될 것이고,

코인이 급상승하는 날짜 사이의 일 수가 X보다 작다면 코인은 X-{코인이 급상승하는 날짜 사이의 일수 } 까지만 떨어지게 됩니다.

 

이분 탐색

문제에서 주어진 N,K(1<=N<=10^6, 1<=K<=10^18)가 크므로 X를 1부터 K까지 모든 수를 찾아보는 방법은 시간이 오래 걸립니다.

그러므로 이분 탐색을 이용해 X값을 구합니다.

 

풀이

이분 탐색

s=0,e=K+1부터 시작해 m=(s+e)//2일 때, 정해진 날짜에 코인을 m원으로 급상승 시켰을 경우 최종적으로 얼마를 현금화할 수 있는지 구합니다.

구해진 현금화 금액이 K보다 크면 e=m, K보다 작으면 s=m으로 두고 반복문을 돌립니다.

 

s<e-1일 동안 반복하고, 최종적으로 e가 답이됩니다.

 

 

해결

이분탐색의 세부적인 요소 설정을 제대로 하지 않아 오래걸렸던 문제입니다...

 

문제 링크 : https://www.acmicpc.net/problem/23978

23978번: 급상승

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/23978.py