[BOJ] 1196번: 잭 바우어

https://www.acmicpc.net/problem/1196

무려 13번 틀리고 맞췄습니다.

일단 식을 알아내야합니다. 제가 볼 때에는 식을 알아내는것도 엄청 쉽지는 않은데, 식을 알아내는게 전체 풀이 과정에서 차지하는 시간 비율이 10%도 안됐던 것 같습니다.

K개의 코드를 모을 때 죽여야하는 사람 수를 알기 위해 일단 K = 1일 때를 생각해봅시다.

1개의 코드를 얻으려면 1명만 죽이면 됩니다.

2개의 코드를 얻으려면 일단 1명을 죽여 코드 1개를 얻고, N/(N-1)명을 죽여 코드 1개를 추가로 얻어야합니다.(N명을 죽였을 때 N-1개의 코드를 얻을 수 있으므로 가능한 식입니다.)

3개의 코드를 얻으려면 일단 1명을 죽여 코드 1개를 얻고, N/(N-1)명을 죽여 두 번째 코드를 얻고, N/(N-2)명을 죽여 마지막 코드를 추가로 얻어야합니다.(N명을 죽였을 때 N-2개의 코드를 얻을 수 있으므로 가능한 식입니다.)

이를 반복하면 K개의 코드를 얻기 위해서

 명을 죽여야함을 알 수 있습니다.

식 까지는 무난하게 구했는데, 문제는 N, K가 최대 10^18입니다. 즉 정직하게 항을 1개씩 더해나가서는 절대 시간 내로 구할 수 없습니다. 이를 위해 필요한 지식이 Harmonic Sequence입니다. 

로 정의가 되고, 죽여야하는 사람수는 N * (H[N] - H[N-K])임을 알 수 있습니다. 또한 H[N]은 

로 근사가 가능합니다. 그러면 H[N], H[N-K]를 근사식으로 구해 N에다가 곱하면 되겠다고 생각하시겠지만, 막상 그렇게 하려고 하면 틀립니다. 바로 double은 필연적으로 오차를 가지고 있기 때문입니다.

예를 들어 1000000000000000000 1 이 들어온 경우를 생각해봅시다. 답은 무조건 1입니다. 그런데 H[N], H[N-K]는 double이기 때문에 오차가 대략 10^-15가 있을 수 있고 여기에 N = 10^18이 곱해지는순간 오차는 까마득하게 커져서 허용 범위를 넘어서게 됩니다. 이를 막기 위해 N을 식 중간중간에 곱하면서 가야하는데, 문제는 log1p 함수로 ln N을 구하는 과정에서 이미 오차가 생겨있습니다. 이를 막기 위해 N보다 K가 많이 작은 경우에는 H[N] - H[N-K]를 한번에 계산해 N * ln(1+K/(N-K))를 taylor series로 계산했습니다.

floating error가 얼마나 껄끄럽고 더러운지를 알 수 있는 문제였습니다.

코드가 정말 답도 없게 더러운데 알아서 잘 참고해주시면 감사하겠습니다.

https://github.com/blisstoner/BOJ/blob/master/1196.cpp