사실 이 문제는 마비노기의 경작 시스템에서 아이디어를 얻은 문제입니다. 실제 모델과 다르다는 출제진 몇 명의 의견이 있었으나 그건 문제에 중요치 않아요..
이 문제는 상수시간 안에 풀 수 있는 문제입니다. 왜냐하면,
여러 번으로 쪼갤 필요 없이 작물을 두 덩어리로 쪼개서 한 덩어리는 수표로 받고 한 덩어리는 계좌로 받아도 됩니다. 수표나 계좌나 어쨌거나 일정 금액 이하를 버림하는 것인데, 이 버림되는 금액을 여러 번 쪼개어 판다고 해서 줄일 수는 없기 때문입니다.
수표로 N - i개의 작물을 팔았고 계좌로 i개의 작물을 팔았다고 가정해 봅시다. 이 때 수표로 받음으로 인해서 버려지는 금액을 k라 하죠. (k = (N - i) * K mod 10000) 이 때 N - j (j > i)개의 작물을 팔아도 k원을 버리게 된다고 가정합시다. 그럼 수표로 인해 버리게 되는 금액은 양쪽이 똑같으니 계좌로 버리게 되는 비용을 생각해보면 될텐데, i < j 에서 당연히 i개 파는 쪽이 계좌로 버리는 비용이 적습니다. 따라서 같은 k에 대해서는 최대한 수표로 많이(계좌로 적게) 팔아보는 것이 유리합니다.
따라서 i를 0에서부터 N까지 증가시키면서 사용된 k를 배열에 표시하였다가, 이미 기존에 k원을 버리는 방법을 고려한 적이 있었다면 더 이상 고려할 필요가 없겠습니다. (아니면, 배열 없이 min(9999, N)까지 증가시켜도 같은 결론을 얻겠죠?)
Being
사실 이 문제는 마비노기의 경작 시스템에서 아이디어를 얻은 문제입니다. 실제 모델과 다르다는 출제진 몇 명의 의견이 있었으나 그건 문제에 중요치 않아요..
이 문제는 상수시간 안에 풀 수 있는 문제입니다. 왜냐하면,
그와 같은 까닭에 간결하게 구현이 가능한 문제였습니다. :)
15년 전