문제 📕

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

접근 방법 🧐

처음 문제를 봤을 때는, 좀 쉽다고 생각했다!

값이 최대일려면, 팁을 많이 주는 사람을 먼저 들어가게 하면 되는 거 아닌가요??

큰 수(팁 금액) - 작은 수(들어간 순서)가 최대잖아!

살짝 찜찜한 1. 시간제한 2초와 2. N과 팁의 범위가 있었지만 그냥 넘어갔다..

1. 팁이 들어있는 int 배열 arr을 내림차순으로 정렬해준다.
2. 문제에서는 "돈 - (받은 등수 - 1)" 이지만, 애초에 입력 받을 때 i, 즉 등수에서 1씩 빼서 배열에 저장했기에 "돈 - 받은 등수"로 처리함
3. 계산식의 값이 들어가는 temp가 음수이면 temp를 으로 바꿔서 결과값에 더해줬다.

---

첫 제출

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		Integer[] arr = new Integer[N];
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr, Comparator.reverseOrder());
		
		int result = 0;
		for(int i=0;i<N;i++) {
			int temp = arr[i]-i;
			if(temp<0) temp = 0;
			result += temp;
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
			
	}
}

아래 최종 코드와 다른 점은

• 결과인 result가 int형
• if(temp<0) temp = 0 이지만, 최종코드에서는 음수일 경우, 아예 break해줌
  

1. result를 long으로 바꿔주고,
2. 팁 계산했더니 음수로 나왔을 경우, 다음 손님들도 음수이기에 굳이 계산할 필요가 없다!
   → break로 시간제한 문제를 해결해줬다.

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		Integer[] arr = new Integer[N];
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr, Comparator.reverseOrder());
		
		long result = 0;
		for(int i=0;i<N;i++) {
			int temp = arr[i]-i;
			if(temp<0) break;
			result += temp;
		}
		
		bw.write(result+"");
		bw.flush();
		bw.close();
			
	}
}

느낀점 📖

쉬운 문제인데, long으로 출력을 해준다던가, 시간 제한을 생각하지 않고 그 뭐지 나이브하게? 일단 코드부터 써! 이런식으로 문제를 풀다보니 자잘한 실수들로 인해 제출을 여러번하게 되는 것 같다.🙄🙄