https://www.acmicpc.net/problem/24893
문제 요약
- 1 ~ N 좌표에 적들이 있고, 1초에 한번씩 이동(N = 10만, 적 = 10^5), 성에는 1씩 데미지를 줌
- 0 좌표에 성이 있고, E 데미지를 받으면 끝(E - 1까지는 버틸 수 있다는 의미, E : 10^8)
- k 명 궁수와 t 주기를 결정할 수 있음
- a k - b t의 최소값 구하기(a, b는 주어짐)
접근법
- 접근하다가 공식해설을 보고 논리 오류를 찾았던 문제
- 이해하기 난해했고, 접근도 어려웠음.
- 일단 k가 엄청 크면 적을 다 막을 수 있고, t가 1일때 k가 적당히 작아져야한다는 것은 알겠음
- ak-bt의 최소값을 구해아하니까, k는 작고 t는 클 수록 좋겠음
- 문제의 테스트케이스를 보고 몇 가지 조건을 도출함
- E가 엄청크면 궁수를 배치 안해도 됨 => 0, 10^9
- K를 적당히 크게 하면 t를 엄청 크게 해도 됨 => 적의 수 - E + 1, 10^9 => 데미지를 E만큼 맞으면 안되니까 궁수를 1명 더 배치해야 안전함
- 이제 t를 생각해봐야겠는데..일단 처음 생각은 t가 1, 2, .. N까지는 되겠다..였음
- 왜 소수는 안될까 고민해봤음
- 궁수는 k명 단위로 끊어지니까 소수가 있더라도 앞이나 뒤에 가까운 정수로 연결될때가 유리하고... 뭐 그럴 것 같음
- t가 1이면 1좌표씩 끊어서 생각하면 되는데
- 처음에는 각각의 좌표중에서 가장 큰 값으로 궁수를 배치하면 되겠다 생각했는데, 테스트케이스를 통해 아닌 것을 깨달음
- 1 좌표를 처리하고 2좌표 이후의 적도 처리가 가능하기 때문에 연속해서 처리할 수 있음을 고려해야함
- 그래서 궁수도 처음부터 열심히 적을 처리하고, 적도 열심히 몰려오는 상황에서 처리 >= 적 을 만족하는지로 판단했음
- t가 2이면 두개씩 묶고, 3이면 세개씩 묶고...
- 이 부분은 결과적으로, t, t 2, t 3의 누적합으로 생각하면 접근이 편해졌음
- n + n/2 + n/3 + ...의 연산이라 복잡도는 괜찮다고 판단함
- 그냥 더하면 힘들것 같아서 부분합을 적용함
- E를 고려해야했음
- 처음에는 궁수들이 앞에서부터 처리를 할 것이기 때문에 가장 뒤에 적부터 E + 1명을 제거하면 되지않을까 생각했고 이 부분이 오류였음
- 왜냐하면 뒤에 전개할 논리에서 특정 값(k')를 정해서 이렇게 해도 적을 처리하는데 무리가 없는지를 판단하는 식으로 전개할텐데
- 중간에 값이 튀는 경우에 대해서는 적절한 대응이 안됨
- 이 부분을 공식 해설을 보면서 오류라는 것을 알게됨
- E를 고려하는 부분을 바로 잡음
- 특정 시점까지 적이 누적해서 몰려왔다고 치면, 누적값 - E + 1명까지는 처리했어야함
- 매 t 주기마다 저 값을 측정함
- E값으로 인해 k값이 더 작아지는 건 아닐까 생각해볼 수도 있는데, 어쨌든 저 k값이 궁수를 배치할 수 있는 "하한" 이라고 생각하면 될 것 같음 => 더 작아지는건 당연히 무리이고, k값이면 적들이 몰려와도 성이 무너지진 않겠다의 의미 => 매 순간 성이 E이상의 데미지는 입지 않으므로
newbieski