[코딩테스트]그리디(큰 수의 법칙)

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

 코딩테스트를 준비하면서 중요하다고 생각하는 문제들을 한번더 상기 시킬겸 블로그에 올리고 있습니다. 처음부터 난이도가 높은 문제는 피하고 있으며, 난이도가 낮은 문제를 기반으로 하나씩 풀어가려고 합니다.

 

1. 큰 수의 법칙

입력 조건

- 첫째 줄에 N(2<=N<=1000),M(1<=M<=10000),K(1<=K<=10000)의 자연수

- 둘째 줄에 N개의 자연수가 주언진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.

- 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력조건

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

 

작성 코드(Java)

import java.util.*;

public class test1 {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		int K = kb.nextInt();
		int[] a = new int[N];
		
		for(int i=0;i<a.length;i++) {
			a[i] = kb.nextInt();
		}
		
		Arrays.sort(a); //배열 a를 오름차순으로 정렬함
        
		int count =0;
		int sum =0;
		for(int g=0;g<M;g++) {
		if(count>=K) {
				sum+=a[N-2];
				count =0;
			}
		else {
			sum+=a[N-1];
			count++;
			}
		}
		System.out.println(sum);
		
	}

}

 

설명

: Scanner를 쓰기위한 import와 클래스를 선언해준다. N,M,K에 대한 정수를 입력받고 a배열에 값을 입력받는다. 배열 a를 Arrays.sort함수로 정렬하여 a[N-1]에는 가장 큰 수가 위치하게된다. 이를 이용하여 조건문을 구성한다.