[Baekjoon] 2790번 F7

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

 

쉽게 생각했다가 시간초과 나온 문제다.

각 운전수마다 모두 비교해가며 1등이 될 수 있는지 판별할 수 있지만,

O(n^2) 의 시간이 걸리기 때문에 시간초과가 뜬다.

 

이 문제는 (역)정렬을 해야 풀린다.

예를 들어보자.

 

5

13 16 13 10 16

 

역정렬하면

16 13 13 13 10 이 된다.

이렇게 두고 문제를 해결하면 이해하기 쉽다. (내가 작성한 코드처럼 굳이 역정렬을 할 필요는 없음)

 

먼저 가장 큰 점수를 갖는 운전수(16)를 찾고 그 점수에 1점을 더해준다.

그 운전수가 가장 적은 점수를 받아야 다른 운전수들이 1등 할 가능성이 열리기 때문이다.

그 값을 max 라고 하자.

 

앞으로 다른 운전수들은 이 max 를 넘는 점수를 받으면 1등이 될 수 있다.

따라서 다른 운전수 점수+n 값이 max 보다 높거나 같으면 count ++ 하고, 낮으면 count 를 올리지 않는다.

 

i=1부터 순회해본다(i=0은 max 이기 때문에 이미 1등할 가능성이 있어서 스킵)

i=1 일 때의 운전수 점수+n 값이 max 값보다 높거나 같으면 count++ 한다.

 

그 다음이 문제임.

i=2 일 때의 운전수는 어떻게 해야 하는가?

생각해보면 i=2 일때의 운전수는 i=0 운전수(max) 에 1점을 주고, i=1 운전수에 그 다음으로 적은 2점을 줄 것이다.

왜냐하면 내림차순이기 때문에 나(i=2)보다 점수가 높은 운전수들의 점수를 최대한 깍아야 하기 때문이다.

 

i=2 운전수는 max 와 i=1 운전수의 점수 + i +1 값을 모두 뛰어넘어야 1등이 가능하다.

(왜 i=1 운전수의 점수 +i +1 인지 한 번 손으로 직접 계산해보라)

 

사실 모두 뛰어넘지 않아도 된다. 둘 중 더 큰 값만 뛰어넘으면 된다.

따라서 max 값을 max = Math.max(max, ( i=1 운전수의 점수 + i + 1 )) 으로 갱신해주고 max 를 넘는지만 봐주면 된다.

 

i=3 운전수는 같은 방식으로 새로 갱신된(i=2 운전수의 점수까지 max 계산에 포함되어져서 갱신) max 값을

넘는지 보면 된다.

 

설명이 난해하나 직접 손으로 써가면서 점수를 계산해보면 의외로 쉽게 이해가 될 것이다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws Exception{

		FastScanner scan = new FastScanner();
		int n = scan.nextInt();
		int max = -1;
		int[] drivers = new int[n];
		for(int i=0; i<n; i++) {
			drivers[i]=scan.nextInt();
			if(max<drivers[i]) max=drivers[i];
		}
		Arrays.sort(drivers);
		max++; //max 값에 얻을 수 있는 가장 작은 점수를 더해주기때문에 +1 해줌.
		int count = 1; //max 값은 언제나 1등할 수 있기 때문에 count 가 1부터 시작.
		for(int i=n-2; i>=0; i--) {
			int a = drivers[i]+n; //a는 n 점수를 받고 1등이 될 수 있는지 보고 싶은 운전수의 점수
			if(max>a) break; //max 를 넘지 못하면 1등이 될 수 없다.
			
			int b = drivers[i]+n-i; //위에 설명 참고
			max=Math.max(max, b); //max 를 새로 고친다. 다음에 나오는 운전수들은 이 점수를 넘어야 1등이 가능하다.
			count++;
		}
		System.out.println(count);
	}
    public static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        public int nextInt() throws Exception {
            if(st == null || !st.hasMoreTokens()){
                st = new StringTokenizer(br.readLine());
            }
            return Integer.parseInt(st.nextToken());
        }
    }
}

 

코드 : http://boj.kr/7cfedf2aca9c42b28ae1856b62a8ad19