[2019 국가 교육기관 코딩 테스트 | 그리디 문제풀이] 큰 수의 법칙

첫 줄에는 숫자 3개가 주어진다. 

각각 아래 배열의 크기, 주어진 수를 몇번 더할 것인지, 같은 수를 몇번 더할 수 있는지 주어진다. 

이를 N,M,K라고 하자. 둘째 줄에는 N개의 숫자가 나열되어 있다. 

같은 수를 K번을 초과하여 반복할 수 없다. 

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

<입력 예시>

5 8 3

2 4 5 4 6

<출력 예시>

46

<문제 풀이>

input = ['5 8 3','2 4 5 4 6']
let M = input[0].split(' ').map(Number)[1] //8
let K = input[0].split(' ').map(Number)[2] //3
let arr = input[1].split(' ').map(Number)

let answer = 0;
arr.sort((a,b)=>a-b)
let first = arr[arr.length-1]
let second = arr[arr.length-2]

while(M>0){
    for( let i = 1; i <= K; i++){
        answer+=first
        M-=1
        if (M === 0) 
        break
    }
    answer+=second
    M-=1
}

console.log(answer)

'그리디' 의 특징은 현재 상황에서 지금 당장 좋은 것만 선택한다. 

'가장 큰 순서대로', '가장 작은 순서대로' 등 문제에 이런 힌트가 대부분 존재한다. 

문제들을 풀어보니, 가장 적절한 예시는 어디든 다 거스름돈을 먼저 예시로 들고 있다. 

거스름돈으로 거슬러 줄 동전의 최소 갯수.. 

 

이 문제도 동일하다. 총 M번을 더할 것인데, 같은 수를 K번 더할 수 있다. 

더할 때마다 M을 차감하고, M이 0이 되면 반복문이 종료된다. 

가장 큰 값을 구하려면 큰 수부터 더해야 하므로, sort를 통해 오름차순으로 정렬한 뒤,

가장 오른쪽 값이 가장 큰 값이므로 해당 값을 first로 두었다. 

answer에 first를 K번 더하고, M을 1씩 차감했다. 만약 M이 0이 되면 종료한다. 

 

first를 3번 더했는데 M이 0이 되지 않았다면, 아래로 내려가서 answer에 second를 더하고,

M을 1을 차감하고, M이 0이 될 때까지 처음으로 돌아가서 반복한다. 

 

많은 문제를 풀어본 것은 아니지만, 이 문제 또한 전형적인 그리디 문제인 것 같다. 

가장 큰 수를 조건에 맞는 만큼 더할 수 있고, 그 다음 수를 더하지만 다시 가장 큰 수를..

아직 쉬운 문제만 풀어서 그런지, 그나마 다른 알고리즘에 비해서 문제 지문을 보았을 때

또렷하게 유형이 보이는 것 같다. 앞으로도 화이팅 ^^