since 2019.

3 minute read

Updated:

프로그램 설명

  • 입력받은 숫자를 사용하여 최대값과 두 번째 큰 값을 찾고, 최대값을 연속해서 K번 더하고 그 다음으로 큰 값을 1씩 더하는 과정을 M번 반복하여 합을 구하는 프로그램이다.

입력 예시

5 8 3

2 4 5 4 6

출력 예시

46

구현 과정 1

  1. 입력값을 문자열로 받아 ‘split();’ 메서드를 통해 공백을 기준으로 분리한다. 분리된 배열의 첫번째 요소는 배열의 크기 N, 두 번째 요소는 숫자가 더해지는 횟수 M, 세 번째 요소는 연속 가능한 횟수 K이다. 반복문을 이용해 ‘N’개의 정수값을 받아서 array에 저장한다.
  2. 배열을 오름차순으로 정렬하고, 최대값과 두번째로 큰 값을 변수에 저장한다.
  3. while문을 돌면서 제일 큰 수와 두 번째로 큰 수를 규칙에 따라 더하고, 합계를 계산한다.

구현 코드 1

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				Scanner sc = new Scanner(System.in);

        // N, M, K를 공백을 기준으로 구분하여 입력 받기
        int N = sc.nextInt(); // 배열의 크기
        int M = sc.nextInt(); // 숫자가 더해지는 횟수
        int K = sc.nextInt(); // 연속 가능한 횟수

        System.out.println(N + "개의 정수를 입력하세요.");
        //배열의 크기를 선언하고, for문을 돌면서 입력한 값을 배열에 하나씩 담는다.
        int[] array = new int[N];
        for(int i=0; i< N; i++){
            array[i] = sc.nextInt();
        }

        //배열값의 최대값, 두번째로 큰 값 구하기 위해 오름차순으로 정렬
        Arrays.sort(array);

        //배열의 최대값과 두번재로 큰값 저장하기
        int fir = array[N-1];
        int sec = array[N-2];
        //합계
        int sum = 0;
        //숫자 더해지는 횟수 카운트
        int count = 1;
        // 제일 큰 수 더한 카운트
        int firCount = 1;

        // 슷자 더해지는 횟수 M만큼 돈다.
        while(count <= M){
            // 제일 큰 수는 연속 가능한 횟수 K만큼 더한다.
            // 더하고 나면, firCount와 전체 카운드를 1씩 올린다.
            if(firCount <= K){
                sum+= fir;
                firCount++;
                count++;
                //System.out.println("fircount: " +  sum);
            }else{
                // 제일 큰 수가 연속 가능한 횟수만큼 더하기가 끝나면, 두 번째 큰 값을 더한다.
                // 전체 횟수 카운트를 1 올리고, 제일 큰 수의 카운트를 1로 초기화하여 두 번째 큰 값은 한 번만 더해지도록 한다.
                sum+= sec;
                count++;
                firCount = 1;
                //System.out.println("seccount: " + sum);
            }
        }
        System.out.println(sum);

    }
}
  • 앞선 코드는 M의 크기가 100억 이상으로 커지면 시간 초과 판정을 받을 수 있다. 수학 아이디어를 통해 효율적인 문제 해결이 가능하다.
  • 반복되는 수열을 파악한다. 가장 큰 수와 두 번째로 큰 수가 더해질 때 특정한 수열 형태로 반복하여 더해진다. {6, 6, 6, 5}가 반복된다. 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.
  • M이 (K+1)로 떨어지지 않는 경우도 고려해 M을 (K+1)로 나눈 나머지를 추가로 더한다.
int(M / (K + 1)) * K + M % (K + 1)

구현 과정2

  1. 함수 내부에서는 입력받은 배열 nums를 내림차순으로 정렬하고, 가장 큰 수와 두 번째로 큰 수를 찾는다.
  2. 이후, 큰 수의 법칙에 따라 가장 큰 수가 더해지는 횟수를 먼저 계산하고, 두 번째로 큰 수를 더해야 하는 횟수를 계산한다.
  3. 최종적으로, 이 두 값을 활용하여 덧셈 결과를 계산하고 반환한다.

구현 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, M, K를 공백을 기준으로 구분하여 입력 받기
        int N = sc.nextInt(); // 배열의 크기
        int M = sc.nextInt(); // 숫자가 더해지는 횟수
        int K = sc.nextInt(); // 연속 가능한 횟수

        System.out.println(N + "개의 정수를 입력하세요.");
        //배열의 크기를 선언하고, for문을 돌면서 입력한 값을 배열에 하나씩 담는다.
        int[] array = new int[N];
        for(int i=0; i< N; i++){
            array[i] = sc.nextInt();
        }

        //배열값의 최대값, 두번째로 큰 값 구하기 위해 오름차순으로 정렬
        Arrays.sort(array);

        //배열의 최대값과 두번재로 큰값 저장하기
        int fir = array[N-1];
        int sec = array[N-2];

        // 가장 큰 수가 더해지는 횟수 계산
        int count = M / (K + 1) * K;
        count += M % (K + 1);

        int result = 0;
        result += count * fir; // 가장 큰 수 더하기
        result += (M - count) * sec; // 두 번째로 큰 수 더하기
        System.out.println(result);
		}
}

You may also enjoy