이것이 취업을 위한 코딩 테스트다. 그리디 [큰 수의 법칙]

이것이 취업을 위한 코딩 테스트다. with 파이썬 - 나동빈

나의 풀이

public class LawOfLargeNumbers {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int answer = 0;
        String str = br.readLine();
        String[] split = str.split(" ");

        int N = Integer.valueOf(split[0]);
        int M = Integer.valueOf(split[1]);
        int K = Integer.valueOf(split[2]);

        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        Arrays.sort(arr);

        int first = arr[N - 1];
        int second = arr[N - 2];
        int temp = K;

        for(int i = 0; i < M; i++) {
            if(temp != 0) {
                answer += first;
            } else {
                answer += second;
                temp = K;
            }

            temp--;
        }

        System.out.println(answer);
    }
}

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int answer = 0;
String str = br.readLine();
String[] split = str.split(" ");

int N = Integer.valueOf(split[0]);
int M = Integer.valueOf(split[1]);
int K = Integer.valueOf(split[2]);

• 우선 입력을 한 줄에 받고, 공백 단위로 입력받은 값을 잘라준다.
• 차례대로 N(입력할 숫자의 갯수), M(총 더할수 있는 횟수), K(한번에 더할 수 있는 횟수)

int[] arr = new int[N];

for(int i = 0; i < N; i++) {
  StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
  arr[i] = Integer.parseInt(stringTokenizer.nextToken());
}

Arrays.sort(arr);

• 사이즈가 N 인 배열을 만들고, 해당 사이즈만큼 숫자를 받아 배열을 작성해준다.
• 그리고 해당 배열을 정렬시켜준다.

int first = arr[N - 1];
int second = arr[N - 2];

• 정렬을 하고나면 뒤로부터 가장 큰 수가 위치하게 된다. 가장 큰 수와 그 다음 큰 수를 변수에 담아둔다.

int temp = K;

for(int i = 0; i < M; i++) {
    if(temp != 0) {
        answer += first;
    } else {
        answer += second;
        temp = K;
    }

    temp--;
}

System.out.println(answer);

• K의 값을 건들지 않기 위해 temp 변수를 하나 정의했다.
• 한번에 더할 수 있는 기회가 남아있다면(temp의 값이 0 이 아닐 떄) 가장 큰 수를 더하고, 기회가 없다면(temp의 값이 0 일 때) 그 다음 큰 수를 더해주고 기회를 다시 초기화한다.
• 모든 연산 후에는 기회를 1씩 빼준다.

문제 해설 & 느낀점

문제를 이렇게 for 문을 돌려서 풀 수도 있지만, M 의 값이 엄청나게 크다면, 이러한 방법은 시간 초과 판정을 받을 것이다. 그러므로 간단한 수학적 아이디어가 필요했다.

이 문제를 보면 반복되는 패턴이 있다는 것을 확인할 수 있다.

• 가장 큰 수 : 6, 다음으로 큰 수 : 5
• M = 8, K = 3
  • (6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = 46

이러한 형태로 일정하게 반복해서 더해지는데, 위의 예에서는 (6 + 6 + 6 + 5) 가 반복되고 있다.

그렇다면 반복되는 수열의 길이는? K + 1 = 4가 되고, M / (K + 1) = 수열의 반복 횟수가 된다. 다시 이 반복 횟수에 K 를 곱해주면 가장 큰 수를 더하는 횟수가 나오게 된다.

이 때 M 이 (K + 1) 로 나누어지지 않는 경우도 있다. 이 경우에는 M 을 (K + 1) 로 나눈 나머지 만큼 가장 큰 수가 더해지기 때문에, M % (K + 1) 를 더하는 횟수에 추가하면 된다.

그다음 큰 수는 (M - 가장 큰 수를 더하는 횟수) 를 하면 저절로 구해진다.

int count = (M / (K + 1)) * K;
count += (M % (K + 1));

answer += first * count;
answer += (M - count) * second;