백준 1758: 알바생 강호 - javascript (그리디)

문제 출처 

https://www.acmicpc.net/problem/1758

1758번: 알바생 강호

 

문제

스타박스는 손님을 입장시킬 때 독특한 방법으로 입장시킨다.

스타박스에서는 손님을 8시가 될 때 까지, 문앞에 줄 세워 놓는다. 그리고 8시가 되는 순간 손님들은 모두 입구에서 커피를 하나씩 받고, 자리로 간다. 강호는 입구에서 커피를 하나씩 주는 역할을 한다.

손님들은 입구에 들어갈 때, 강호에게 팁을 준다. 손님들은 자기가 커피를 몇 번째 받는지에 따라 팁을 다른 액수로 강호에게 준다. 각 손님은 강호에게 원래 주려고 생각했던 돈 - (받은 등수 - 1) 만큼의 팁을 강호에게 준다. 만약, 위의 식으로 나온 값이 음수라면, 강호는 팁을 받을 수 없다.

예를 들어, 민호는 팁을 3원 주려고 했고, 재필이는 팁을 2원, 주현이가 팁을 1원 주려고 한 경우를 생각해보자.

민호, 재필, 주현이 순서대로 줄을 서있다면, 민호는 강호에게 3-(1-1) = 3원, 재필이는 2-(2-1) = 1원, 주현이는 1-(3-1) = -1원을 팁으로 주게 된다. 주현이는 음수이기 때문에, 강호에게 팁을 주지 않는다. 따라서, 강호는 팁을 3+1+0=4원을 받게 된다.

스타박스 앞에 있는 사람의 수 N과, 각 사람이 주려고 생각하는 팁이 주어질 때, 손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 잇는 팁의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.

출력

강호가 받을 수 있는 팁의 최댓값을 출력한다.

예제 입력 1 복사

4
3
3
3
3

예제 출력 1 복사

6

예제 입력 2 복사

3
3
2
3

예제 출력 2 복사

5

예제 입력 3 복사

5
7
8
6
9
10

예제 출력 3 복사

30

예제 입력 4 복사

5
1
1
1
1
2

예제 출력 4 복사

2

예제 입력 5 복사

3
1
2
3

예제 출력 5 복사

4

정답 풀이 힌트 

문제를 이해한다면

- 0번째 사람은 생각한 팁에서 -0 을 뺀 팁을 준다. 

- 1번째 사람은 생각한 팁에서 -1을 뺀 팁을 준다. 

- 2번째 사람은 생각한 팁에서 -2를 뺀 팁을 준다. 

- 3번째 사람은 생각한 팁에서 -3을 뺀 팁을 준다. 

1) 주어진 팁들은 내림차순 정렬 

2) 생각한 팁에서 자기 순서만큼 값을 뺀다. 

3) 2번의 팁이 양수 일 때만 sum 값에 더한다. 

문제 풀이 코드 

let input= require('fs').readFileSync('/dev/stdin').toString().split('\n'); 
let N = Number(input.shift()); 
let tips = input.map(v=> Number(v)).sort((a,b)=> b-a); 
let sum = 0; 
for(let i=0; i<N; i++){
    if(tips[i] - i > 0){
        sum+= (tips[i] - i); 
    } 
}
console.log(sum);

의사 코드 추가 

let input= require('fs').readFileSync('/dev/stdin').toString().split('\n'); 
let N = Number(input.shift()); //몇명?
let tips = input.map(v=> Number(v)).sort((a,b)=> b-a); //숫자 타입으로 변환, 내림차순 정렬 
let sum = 0; //팁의 최댓값
for(let i=0; i<N; i++){
    if(tips[i] - i > 0){ //주려는 팁이 양수일 때만 더해준다. 
        sum+= (tips[i] - i);   
    } 
}
console.log(sum);