[그리디] 큰 수의 법칙

난이도 ♦︎♢♢ | 풀이시간 30분 | 시간제한 1초 | 메모리제한 128MB | 기출 2019 국가 교육기관 코딩테스트

 

[문제]

출제자는 큰 수의 법칙을 본인만의 방식으로 다르게 사용하고 있다. 이 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙이다.

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

 

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 출제자의 큰 수의 법칙에 따른 결과를 출력하시오.

 

[입력조건]

• 첫째 줄에 N(2 <= N <= 1,000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

[출력조건]

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

[해설]

• 가장 큰 수와 두번째로 큰 수를 저장하여 가장 큰 수를 K 번 더한 후 두번째 큰 수를 한번 더하는 것을 반복한다.

[소스코드] - 연습 풀이

# n: 배열의 크기 m : 더해지는 횟수  k : 하나당 연속 k 번까지 더해질 수 있음.
# 첫째줄 : n,m,k를 입력받는다
n, m, k = map(int, input().split())
# 둘째줄 : 리스트를 입력받는다.
nlist = list(map(int, input().split()))

# 최종 더해질 변수를 정의한다.
sum = 0

# 리스트를 크기 순으로 정렬한다.
nlist.sort()

# 가장 큰수와 두번째로 큰 수를 구한다
first = nlist[-1]
second = nlist[-2]

# (가장 큰수 * k ) + 두번째로 큰수 를 반복할 횟수를 구하기 위해 몫을 구한다.
mul = m // (k+1) 

sum += ((first * k) + second) * mul

# 추가로 반복해야하는 횟수를 구하여 가장 큰수를 추가로 더해준다.
sum += first * (m - ( (k+1) * mul ))

print(sum)

[소스코드] - 해설

n, m, k = map(int, input().split())
nlist = list(map(int, input().split()))
sum = 0

nlist.sort()
first = nlist[n-1]
second = nlist[n-2]

# 가장 큰수를 더해야할 횟수를 구한다
count = int(m / (k+1)) * k
count += m % (k+1)

# 가장 큰 수를 더해야하는 만큼 먼저 더한다.
sum += count * first
# 남은 m 만큼 두번째 큰 수를 더한다
sum += (m-count) * second

print(sum)

 

[느낀점]

처음에 너무 어렵게만 생각해서 그런지 돌고 돌아서 코드를 저렇게 작성했었는데 책에 있는 코드를 보니까 한결 편하게 풀 수 있었다.

계산하는 것이 메모리나 속도에 영향을 줄 수 있으니까 신중하게 계산을 덜 할 수 있는 방향으로 더욱 코드를 고민해봐야할 것 같다.

접근 방법은 좋았으니 문제를 풀때에 더하기보다는 곱하기를 이용하는 등 조금 더 간편화 할수 있는 계산들에 대해서도 생각해봐야 할것같다.