큰 수의 법칙 ( 2019 국가 교육기관 코딩 테스트 )

1. 문제 설명

특정한 배열이 있다. 주어진 규칙은 M번을 더하여 가장 큰 숫자를 만드는 것이고, 이 때 같은 인덱스에 해당하는 숫자를 최대 K번 까지만 반복하여 더할 수 있다고 한다.

 

예를 들어 배열 [ 2, 5, 4, 3, 2 ] 가 주어지고, M = 8, K = 3 이라고 주어지면, 8번을 더해 가장 큰 숫자를 만드는 경우이다. 이 때 최대 3번의 반복만큼 하나의 인덱스 숫자에 대해 덧셈이 허용된다.

 

즉, 5 + 5 + 5 + 4 + 5 + 5 + 5 + 4 = 38 이 가장 큰 숫자가 된다.

 

반면, 배열 [ 3, 5, 3, 5, 3 ] 이 주어지고, 같은 K, M이 주어질 때 가장 큰 숫자는 다음과 같다.

 

( 5 + 5 + 5 ) + ( 5 + 5 + 5 ) + 5 + 5 = 40 이 가장 큰 숫자가 된다.

 

가장 큰 값에 해당하는 원소가 서로 다른 인덱스에 위치한 경우, 번갈아 가며 사용을 허용한다.

2. 문제 풀이

위에서 설명한 예제 그대로 코드에 옮겨보자.

 

중요한 아이디어는

     - 가장 큰 값의 원소를 무조건 K번 반복하게 하는 것, 그리고 두 번째로 큰 원소를 1번 더하는 것

     - 위 로직을 M == 0이 될 때 까지 반복한다

 

M만큼 반복문을 설정하고, 위 아이디어를 해당 반복문에 삽입하면 된다. 

 

코드로 구현하면 다음과 같다.

입력값을 얻고, 입력된 배열을 먼저 정렬 하고 나서 가장 큰 값의 원소와 두 번째로 큰 값의 원소를 추출한다.

결과값을 선언한 후, 로직에 따라 구현된 부분에 따라 값을 더한 후 출력한다.

 

이걸 더 응용하여 생각하면, K번 반복되어 더해지는 가장 큰 수와 한 번 씩 더해지는 두 번째로 큰 수를 한 묶음으로 생각할 수 있다.

이 묶음의 길이는 K + 1로 생각할 수 있고, M을 이 길이로 나눈 몫이 바로 수열이 반복되는 횟수가 된다.

 

그 수열이 반복되는 횟수에서 다시 K를 곱한 값이 바로 가장 큰 수가 더해진 횟수가 된다. 

 

하지만 M이 K + 1로 나눠지지 않을 경우도 존재하여, 그 때 나머지만큼 가장 큰 수가 추가적으로 더해진다.

 

이를 최종 계산하면,

     - 가장 큰 수가 더해진 횟수 = int(M / (K + 1)) * K + M % ( K + 1 )

     - 두 번째로 큰 수가 더해지는 횟수 = M - ( 가장 큰 수가 더해진 횟수 )

     - 최종 결과 = 가장 큰 수 더해진 횟수 * 가장 큰 수 + 두 번째로 큰 수가 더해진 횟수 * 두 번쨰로 큰 수

 

이를 코드로 구현하면,

 

3. 느낀 점

Python에서 입력값을 map으로 한번에 입력받을 수 있음을 배웠다.

마찬가지로 배열 역시 해당 코드를 list에 넣어서 선언할 수 있음을 배울 수 있었다.

 

Greedy는 최소, 최대, 가장 ~한 이라는 조건을 잘 살피고, 해당 문제가 Greedy한 해결법이 있는지 고민해보아야 한다.