[BOJ 23978] 백준 23978번 - 급상승

January 6, 2022

		Zero One Algorithm Contest 2021 풀이
A		[BOJ 23971] ZOAC 4
B		[BOJ 23972] 악마의 제안
C		[BOJ 23973] 표적지 옮기기
D		[BOJ 23974] 짝수 게임
F		[BOJ 23976] 문자열 나누기
G		[BOJ 23977] To Find Password
H		[BOJ 23978] 급상승

1. 문제

$23978$. 급상승 (Zero One Algorithm Contest 2021 Open Contest H번)

백준 23978번 - 급상승 (https://www.acmicpc.net/problem/23978)

$X$의 값에 따라서 $0$원이 되기까지의 합이 달라지기 때문에, $X$가 변함에 따라 현금화하는 금액이 달라지고 미리 계산이 불가능하다.

$K$의 범위가 매우 크며, $(K\leq 10^{18})$ $X$가 증가하면 현금화 금액이 증가하고, $X$가 감소하면 현금화 금액이 감소하는데 $K$이상이 되는 $X$값을 찾아야 한다. 따라서 Binary Search(이분탐색)을 생각할 수 있다.

$1\leq K$이므로, 탐색 최저값 left = 1로 설정한다.

$N=1, K=10^{18}, A=1$인 경우($A$는 어떤 값이든 상관없다),

$K\leq X \times (X + 1) / 2$ 이어야 하므로,

$K = 10^{18} $ $\leq X \times (X + 1) / 2 $ $\leq (X + 1)^2 / 2$

$2 \times 10^{18} \leq (X + 1)^2$

$\sqrt{2} \times 10^9 \leq X + 1$

$1.414 \times 10^9 - 1 \lt X$

따라서, 탐색 최고값을 $15$억 정도로 설정하면 된다.

합은 $X$가 $min$(차이값, $X$)만큼 있고, 거기서 ‘$1$부터 (차이값)$-1$ 까지의 합’만큼 빼는 식으로 계산한다. 마지막 날짜는 따로 ‘$1$부터 마지막 날짜 까지의 합’을 더해준다.

boj-23978

마지막 날짜에서 $0$이 되는 과정의 합을 잘못 계산해서 WA를 받았다.