Idea

현재 상황에서 가장 좋은 것을 고르는 방법

동전문제

500원, 100원 , 50원, 10원이 있다고 했을 때 거스름돈의 갯수?

--> 가장 큰 동전부터 차례로 뺸다.

동전 문제의 경우 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들을 종합해서 다른 해가 나올 수 없기 때문에 성립한다.

ex) 500원 400원 100원 일 경우 400원이 500원의 배수가 아니므로 가장 큰 동전부터 빼면 정답에 맞지 않는다.

code

public class GreedyCoinPage90 {

    public static void main(String args[]){
        int n = 1260;
        int count =0;
        int coins[] = {500,100,50,10};

        for(int i : coins){
            count += n/i;
            n %= i;
        }
        System.out.println(count);
    }
}

if 500 , 100, 50 , 10 이라고 생각하기 쉬운데, enhanced for loop를 이용해서 훨씬 쉽게 구현이 가능하다.

기출문제 #1

길이가 n인 배열이 주어진다고 가정했을 때 배열의 값의 합을 M번까지 더해서 최대값을 만들어라. 단 하나의 값에 대해서 최대 연속적으로 K번까지만 더할 수 있다.

ex) [2,4,5,4,6] M=8, K=3 -> 6+6+6+5+6+6+6+5 = 46

풀이

Problem
n개 , m번더하기, 최대 k번
loop 돌려서 최대값 찾는다
k번 더한다 ( k 번 까지 )
그 다음에 loop 돌려서 그 다음 최대값 찾는다
(만약 값이 같다면 그냥 x n 해준다)
그 값을 cash에 저장하고 cash를 한번 더해준후 다시
k번 더한
더할때마다count++를 해주어서 count를 세준다
count = m 이면 멈춘다.

Pseudo code

while{
	
for i <- 0 to k
if(count = max) break;
result = result + max_value 
count++

Find_next_max in array

if(next_max == max_value)
return result = max_value * m

cash= next_max
}

전체코드

public class GreedyLawOfGreatNumbersPage92 {
    public static void main(String args[]){
        int[] data = {2,4,5,4,6};

        System.out.println(findResult(data,8,3));

    }
    static int findResult(int data[], int m, int k){
        int count=0;
        int max=0;
        int next_max=0;
        int temp_count=0;
        int temp_array[] = new int[data.length];
        int result=0;

        // 최대값 찾기
        for(int i =0; i<data.length;i++){
            if(max<data[i]){
                max=data[i];
            }
        }
        // 두번째 최대값 찾기
        for(int i =0; i<data.length;i++){
            temp_array[i]=data[i];
            if(temp_array[i]==max){
                temp_array[i]=-1;
                temp_count++;
            }
            if(temp_count>=2){
                return max*m;
            }
            for(int j =0; j<data.length;j++){
                if(next_max <temp_array[j] && temp_array[j]>0){
                    next_max=temp_array[j];
                }
            }
        }

        while(count<m){
            for(int i=0;i<k;i++){
                if(count==m) break;
                result = result + max;
                count++;
            }
            result=result+next_max;
            count++;
        }
        return result;
    }
}

두번째 값 찾는게 좀 까다로웠는데, 풀이보니까 그냥 sort해서 찾으면 되는거였다.

해설의 다른 방법

첫번째 두번째만 반복 되고, 그 loop의 길이는 K+1이다. 만약 loop로 나누어 떨어지지 않는다면 남는 숫자만큼 최대값을 곱해서 더해주면 된다.

ex) 위의 예시 2,4,5,4,6 --> 6+6+6+5 가 한 loop. 만약 M이 11이면 2loop + (11%4) * 6 가 정답.