그리드 알고리즘 문제 풀이

 

백준에서 가져온 문제이다.

 

사람마다 인출 시간이 다르기 때문에 인출 시간이 제일 긴 사람이 첫 번째로 줄을 선다면 전체 총 합이 커지기 때문에 오름 차순으로 정렬하는 것을 1순위로 생각했다.

 

오름차순 정렬 후 계산을 하면 홈페이지 문제 예시를 예로 들어 5명의 사람이 각각 1 2 3 3 4 분의 인출 시간을 가지고 있으며, 단순 계산식으로 표현하면

 

1

1+2

1+2+3

1+2+3+3

1+2+3+3+4

 

형태로 표현할 수 있다. 각 사람마다 앞에 사람의 인출하는데 걸리는 시간만큼 더 추가로 걸리기 때문이다.

간단하게 표현하자면

1*5 + 2*4 + 3*3 + 3*2 +4

N*인출시간 + (N-1)*다음 사람의 인출시간 .....  이처럼 표현 가능하기에

 

 

이렇게 구현하였다.