11399번: ATM

Memo

• g++ 은 똑똑해서 algorithm 헤더를 추가하지 않아도 sort()함수를 알아서 찾아준다...???
• 처음엔 dp배열을 만들어서 memorization을 해줘야 하나 고민했었다.

입력이 아래와 같이 들어온다. 우리는 모든 사람이 기다리는 시간의 최소값을 구해야한다.

5
3 1 4 3 2

반복문을 돌려서 모두 더하는 방법

가장 쉽게 생각할 수 있는 해결법은 들어온 배열을 오름차순으로 정렬한 뒤 루프를 돌면서 처음부터 해당 위치의 값을 더하면 된다. 이 경우에는 아래와 같이 생각할 수 있다.

sorting 후
-> 1 2 3 3 4

Loop
1 : 1
2 : 1 + 2
3 : 1 + 2 + 3
4 : 1 + 2 + 3 + 3
5 : 1 + 2 + 3 + 3 + 4 

다 더하면 32

나오는 기준으로 곱해서 계산하기

sorting 후
-> 1 2 3 3 4

아래처럼 계산해야 하므로
1 : 1
2 : 1 + 2
3 : 1 + 2 + 3
4 : 1 + 2 + 3 + 3
5 : 1 + 2 + 3 + 3 + 4 
   5번 |4번 |3번 |2번 |1번
이 반복문을 곱셈식으로 바꾸면

result = (1 * 5) + (2 * 4) + (3 * 3) + (3 * 2) + (4 * 1);

Code