[이.코.테] 2. 동빈이의 큰 수의 법칙

문제

동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다.

예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는

6 + 6 + 6 + 5 + 6 + 6 +6 +5인 46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자.

이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이가능하다.

결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

 

입력 조건

• 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

먼저 풀이 방법을 한번 생각 해보겠습니다. 

 

가장 큰 수를 만들면 되기 때문에, 사실 값이 적은 값들은 생각 할 필요가 없습니다. 

 

가장 큰 값들을 K번 더해준 후, 그 다음으로 큰 수를 1번, 또 가장 큰 수를 K 번 더해주는 방식으로 M번 더해주면 되겠습니다. 

 

따라서 이번 풀이에는 정렬을 사용하였습니다. 

 

소스코드 ( Java )

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N =Integer.parseInt(st.nextToken()); //배열의 개수
    int M =Integer.parseInt(st.nextToken()); // 더하는 횟수
    int K = Integer.parseInt(st.nextToken()); // 최대로 더할 수 있는 수
    st = new StringTokenizer(br.readLine());
    int result = 0;
    int[]arr = new int[N];
    for (int i = 0; i <N ; i++) {
        arr[i] = Integer.parseInt(st.nextToken()); //배열 입력
    }
    Arrays.sort(arr); //정렬
    int count = 0;
    for (int i = 0; i <M ; i++) {
        count++;
        if(count % K == 0 ){
            result += arr[N-2];
        }
        else{
            result += arr[N-1];

        }
    }
    System.out.println("result = " + result);
}

배열을 입력 받아 정렬 한 후 ,  M번 동안 반복을 진행합니다.

 

count(연산 횟수) 가 K로 나누어 떨어진다는 뜻은 곧 count 가 K와 같은 숫자가 되었다는 뜻이고,

 

그 경우 가장 큰 수 arr[N-1]이 아닌, 두 번째 큰 수 arr[N-2]를 더해 줍니다. 

 

그 외에는 모두 가장 큰 수를 더하고, count 변수의 값을 증가시키면 되겠습니다.