BILLS

<문제 링크>

https://algospot.com/judge/problem/read/BILLS

 

문제

After being retired from ACM-ICPC, Mr. R decided to quit studying computer science to become a farmer. This year, he harvested N  cabbages, and the price of one cabbage is K  won. R wants to sell all of these cabbages to the Farm Co-Op, but the Farm Co-Op has a rather complicated purchasing policy:

1. R can split the cabbages into any number of bunches, and sell them separately.
2. Every time R cells a bunch of cabbages, he has two ways to collect his earnings:
   1. He can get a check: however, checks can be issued only for amounts multiple of 10,000 won, and the remaining money will be thrown away.
   2. He can get the money wired to his bank account: however, the bank will take 10% as transaction fee and round down the remaining money to the nearest won.

So, how much money can Mr.R can get at most by selling all of the cabbages?

 

풀이

N개의 양배추를 파는데 양배추 한개의 가격은 K원이다. 수표를 사용하면 만원단위 아래의 금액은 버려지고 은행을 이용해 현금으로 팔경우 10프로를 때인다. 양배추를 팔때 N개를 임의로 나누어서 팔 수 있다.

 

우선 문제를 단순하게 생각해보면 이러하다.

N개의 양배추가 있고 이중 i개를 현금으로 판다. 그리고 나머지 n - i개를 수표로 판다 이때 판매금액은 아래와같다

i * k * 0.9 + (n - i) * k / 10000 * 10000

위의 값이 최대가 되는 i를 찾으면 된다 이를 위해 i를 0부터 N까지 순회하여 완전탐색을 통해 원하는 결과를 얻을 수 있다. 하지만 N의 제약이 1억으므로 위와같은 코드는 제한시간내에 원하는 결과를 얻어내지 못한다.

 

문제 해결을 위해서 우리는 문제를 더 간단하게 변형 시킬 필요가 있다.

우리가 구해야할 값은 위에서 구하는 최댓값이지만 위의 최댓값을 구하기 위해서는 판매시 발생하는 손해를 최소화 하면 된다. 우리는 바로 최소로 만들 값에 집중한다.

판매를 할때 발생하는 손해액은 아래와 같다.

i * k * 0.1 + (n - i) * k % 10000

위의 값은 i에 의해서 결정되는데 첫번째 항의값은 i가 클수록 커지고 오른쪽은 i가 클수록 작아진다. 그렇기 때문에 우리는 적당한 i값이 필요한 셈이다. 여기서 주목할 것은 오른쪽 값의 범위가 0 ~ 9999라는 것이다. i가 정해지면 우측 값이 정해지는데 우측값은 최대한 많아도 9999개 밖에 없다는 뜻이다. 지금까지 말한 우측값을 x라고 하고 아래와 같은 배열을 정의하자.

dp[x] = 우측값이 x가 되는 i의 값. 즉 수표로 판매할때 발생하는 손해가 x일때 현금으로 판매되는 양배추의 갯수 i가 저장된다.

여기서 조금더 최적하가 가능하다. 우리는 한번 구해놓은 dp배열의 인덱스를 다시 참조하게 되는순간 dp배열의 초기화를 중단하면된다. 그 이유는 이러하다.

수표로 판매를 할때 발생하는 손해는 (% 10000) 연산으로 구해지게되는데 같은 수 k를 계속해서 더하고 여기에 10000이라는 같은 수를 계속나누게 되면 언젠가는 나머지가 같아질 것이고 나머지가 한번 같아지고 나면 여기서 또 k를 더하고 10000으로 나누면 다음 인덱스에 있는 나머지가 나올것이 자명한 사실이다. 하지만 앞에서 보았듯이 수표로인해 생기는 손해는 그대로인데 현금으로 판매하는 양배추의 수가 더 크다면 결과적으로는 우측항은 그대로지만 좌측항이 더큰 결과를 초래한다. 결국 답이 될 수 없는 값이고 이후의 연산도 그러하다. 그러므로 여기서 dp의 초기화를 멈추고 dp를 순회하면서 최소가되는 결과값을 구하면 답이된다.

시간복잡도는 dp를 초기화하는데 O(10000) 그리고 최소가 되는 결과값을 구하는데 O(10000)이 되어 결과적으로 O(1)이 된다.