[1758번] 알바생 강호

문제 기출 : [https://www.acmicpc.net/problem/1758]

 

 

풀이 방법

[그리디알고리즘] 접근   당연하게 받은 등수가 높을 수록 강호가 받을 수 있는 팁은 줄어든다. 그렇기 때문에 생각한 팁이 높은 순서대로 앞으로 순서를 정해야한다.   그러므로 sort가 먼저 이루어지고 높은 팁을 생각한 사람 먼저 팁을 계산하여 음수가 나오면 앞으로 계속 음수일 것이므로 break문을 걸어둔다.   여기서 내가 30분동안 고민했던 난관. 왜 answer, 즉 팁의 최대값은 long이어야 하는가? int의 범위는 -2147483648 ~ 2147483647 이다. 문제의 팁의 최대값의 최대값은 계산해보니 705082703로 나온다. 그러므로 int형으로도 충분히 커버 칠 수 있어야하는 걸로 보이는데...왜 long을 써야하는가...ㅠㅠ 내가 구한 705082703가 아니라 훨신 더 큰 수가 나올 수 있나..ㅠㅠ?? 찝찝....

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long answer = 0;

		try {
			int N = Integer.parseInt(br.readLine());
			int[] tips = new int[N];

			for (int i = 0; i < N; i++) {
				tips[i] = Integer.parseInt(br.readLine());
			}

			Arrays.sort(tips);

			int tip = 0;
			for (int i = N - 1; i > -1; i--) {
				tip = tips[i] - (N - i - 1);

				if (tip < 0) {
					break;
				}

				answer += tip;
			}

			System.out.println(answer);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}