Wedding Planner
submission : 31 , accepted : 3
AC ratio : 9.68%
Writer : legend12
나름 출제된 문제 중에는 중하위 쪽에 속하는 난이도로 출제가 된 문제인데 (비록 실제 위치는 뒤쪽에 위치하였지만) 문제를 읽으신분이 많지 않은건지 아니면 세부 statement 들을 놓치고 풀다가 틀려서 인지 정답률이 굉장히 낮게 나왔네요 ㅠ
대회 중간 난이도 조절을 위해서 critical 한 부분들에 대해서 broadcast 로 안내를 했는데 다들 보시고 힌트를 얻으셨는지 모르겠네요.
그래도 3팀이나 풀어주시고 해서 다행입니다 하악 -0-

• 문제 설명 JongMan 은 결혼날을 잡으려고 하는데, 최대한 많은 축의금을 받고 싶어합니다. 결혼식에 오는 하객들은 모두 그해 수입의 0.1%를 축의금으로 지불하며, 하객들의 연봉은 태어날때부터 정해져 있고(= 태어날때부터 일을 합니다!), 매해 일정량만큼 증감합니다. 그리고 은퇴시기가 정해져 있어서 해당나이가 되면, 은퇴를 하고 연금만을 받으며, 이 연금은 은퇴하기 직전의 5년간의 연봉의 평균치를 기준으로 받습니다. 사람들은 죽지않고 무한히 산다고 했을때 JongMan 이 기대할 수 있는 최대의 축의금을 찾아주면 되는 문제입니다.
• 해법 하객들의 축의금 그래프는 은퇴전과 은퇴 후의 2개의 구간에 대해서 각각 1차방정식으로 표현이 가능합니다. 따라서 JongMan 이 기대할 수 있는 축의금을 총합 역시 (하객의 총수 + 1)개의 구간에 대해서 각각 1차방정식으로 표현이 됩니다. 위의 그래프를 보시면 구간 분할이 가능합니다. 따라서, 각 구간들에 대해서 최대값들을 구한 후에 그 중에 최대의 값을 취하면 원하는 답을 얻을 수 있습니다. 그러므로 알고리즘의 시간 복잡도는 O(N^2) 이 됩니다. 구간을 나누지 않고 문제를 접근하게 되면 O(NM) 이 되는데 이 경우 시간이 너무 오래 걸리기 때문에 제한 시간내에 원하는 해답을 얻을 수 없으니 주의하여야 합니다. (N = 1,000 / M = 1,000,000) 답을 구하는 과정에서 주의하여야 할 점은 계산 과정상에서 int32 로는 오버플로우가 발생한다는 점입니다. 애초에 정확도를 다소 포기하고 (유효자리수 문제는 발생하지 않습니다.) double 로 연산을 하거나 int64 로 연산 한 후에 최종적으로 출력할때 0.1% 의 축의금 작업을 하는 것이 올바른 답을 구하는데 도움이 될 것 입니다. 추가적으로 int64 로 계산할때 연금을 계산할 때는 5년간의 평균값을 구하기 위해 다 더한 후 5로 나누기 보다는 3년째의 연봉을 취하면 바로 연금값을 구할 수 있으니 정수 연산에 도움이 됩니다 ^_^
• Critical point 여기서 부터 악플 위협을 느끼는중 ㅠ 대부분 broadcasting 된 내용이지만 ㅠ
  1. 입력으로 들어온 하객의 나이가 은퇴시기까지 5년이 채 남아있지 않은 경우, => change rate 연산을 통해서 연금 계산을 해주어야 합니다.
  2. 입력으로 들어온 하객의 나이가 은퇴 후일 경우, (제일 많이 틀리셨을거라 예상중 -0-) => input spec 을 잘 보시면 current salary 가 아닌 current income 입니다. 이부분은 clar 로도 날아왔었지만, 이미 언급되지 않은 상태에서 맞추신 분들이 있는 관계로 read carefully 로 답변을 드렸는데요. 은퇴 시기 이후의 수입은 연금이 되겠지요. 따라서 들어온 입력의 change rate 는 무의미한 값이 됩니다. 이 하객의 경우는 x 축과 평행한 그래프 1개로 생각을 하셔야 합니다. 엄한 문제에 낚여서 고생하신 분들께는 애도의 말씀을 ㅠ 레퍼런스 코드는 잠시 후에 업로드를
     [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]