[Algospot] 마력

문제 정보

문제ID

MAGICPOWER

출제자

mjy0503

출처

2013 KAIST 교내 대회

시간제한

10000ms

메모리제한

65536kb

분류

구현, 그리디

문제 설명

N개의 아이템, M개의 횟수가 주어졌을 때 아이템을 사용하여 얻을 수 있는 최대 마력의 양을 맞추는 문제입니다.
각 아이템은 한번에 얻을 수 있는 마력이 수로 표시 되며, 해당 수는 한번의 사용시 마다 1씩 줄어듭니다.

문제 풀이

매번 그 상황에 가장 큰 값을 가지고 있는 아이템을 선택해 나가면 문제를 해결할 수 있습니다.
즉, 아이템을 정렬한 후 가장 큰 값을 선택하고, 다시 정렬한다음 큰 값을 선택하는 식으로 문제를 해결해 나갈 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

여기서 조금만 더 생각을 하면, 매번 정렬할 필요가 없다는 것을 알 수 있습니다.

가장 큰 값을 가진 아이템을 1회 사용했을 경우 줄어드는 숫자는 1이므로, 해당 아이템은 가장 큰 값을 가지고 있거나 혹은 두번째로 숫자가 많은 아이템과 동률로 가장 큰 값을 가지고 있을 것입니다.

이를 이용해 처음 한번 정렬한 후에 가장 큰 값을 가지고 있던 아이템을 계속해서 공동 1위가 될 수 있도록 공동 1위들의 아이템들을 한꺼번에 더해줘가며 답을 찾으면 됩니다.

n=3, m=3 입력이 3, 2, 4인 예제를 예를 들어 보겠습니다.

Item	비고
3 2 4	초기 상태
4 3 2	정렬
3 3 2	마력 4인 아이템 1개 사용(마력:4*1=4)
2 2 2	마력 3인 아이템 2개 사용(마력:3*2=6)

위와같이 1 ~ p 까지의 아이템이 공동 1위, 가장 큰 값을 가지고 있는 아이템들이라고 한다면,
앞으로 남은 사용 횟수 m이 p 보다 클 경우 p*item[p] 값을 더해준 후 m-p를 해가며 반복 후, m이 p 보다 작을 경우 마지막으로 m*item[p] 값을 더해주면 원하는 값을 구할 수 있습니다.

== 소스보기 ==

결과

#

454339

문제

MAGICPOWER

언어

cpp

길이

598B

수행시간

3ms

결과

정답

제출일

2016-08-08