문제
다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속 K번 초과하여 더해질 수 없다.
예시
예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.
입력 조건
1. 첫째 줄에 N (2<=N<=1,000), M (1<=M<=10,000), K (1<=K<=10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분.
2. 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어짐.
3. 입력으로 주어지는 K는 항상 M보다 작거나 같다. 배열의 크기를 초과하면 안 되기 때문
내 코드
N,M,K = map(int, input().split())
num_list = list(map(int, input().split()))
num_list.sort(reverse=1)
lg_number = num_list[0]
next_lg_number = num_list[1]
differ = lg_number - next_lg_number
dst = [lg_number]*M
result = sum(dst) - (differ*int(M/(K+1)))
print(result)
해설 이 문제의 가장 큰 핵심은, 어느 길이의 배열이 와도 가장 큰 수와 그 다음으로 큰 수 두 개만 사용된다는 점이다. 가장 큰 수를 N만큼 깔고, K+1번 째에 그 다음으로 큰 수로 대치시켜 주면 되는 것이다. 처음엔 배열을 펼쳐 직접 반복문을 통해 인덱스를 제어하려 했다. 그러나 결국은 총합을 구하는 문제이기 때문에 '횟수'에 초점을 두었다. 입력받은 배열을 정렬하여 가장 큰 수와 그 다음으로 큰 수를 찾았다. 그 후 가장 큰 수로 매핑된 배열의 총합에서 두 수의 차 (differ)만큼 빼주었다. 이 때 빼준 횟수는 전체배열 길이 M 중 (K+1)을 나눈 몫이다.
교재 코드 : 교재 코드는 단순 연산을 풀어놓은 임시 코드와 알고리즘을 적용한 코드 총 두 가지가 존재한다.
# 코드1
n,m,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
result = 0
while True:
for i in range(k):
if m==0:
break
result += first
m -= 1
if m==0:
break
result += second
m -= 1
print(result)# 코드2
n,m,k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
first = data[n-1]
second = data[n-2]
count = int(m/(k+1))*k
count += m% (k+1)
result = 0
result += (count) * first
result += (m-count) * second
print(result)
교재해설 가장 큰 수와 그 다음으로 큰 수만으로 결과를 도출해 내는 아이디어는 동일했다. 교재에서 또한 수열의 반복성에 초점을 맞추었다. 차이점이 있다면 Sum함수를 통해 총합을 구한 후 (차이*횟수)를 뺀 내 코드와 달리 교재의 코드는 0에서부터 제일 큰 수와 그 다음으로 큰 수를 각각 더해주고 있다는 점이다.
연산 시간도 측정해 보았다. 상대적으로 내가 구성한 코드의 연산 시간이 가장 빠른 것을 확인할 수 있었다. 아마 msec 단위로 나타나는 듯 한데, 구성한 알고리즘에 따라 M의 크기가 기하급수적으로 크면 시간 초과 판정을 받을 수도 있다고 한다.
평가 아직 초반 단계라 난이도 자체는 그리 어렵지 않은 듯 했다. 또한 문제를 관통하는 아이디어를 얼마나 빨리 떠올리는지의 중요성을 알 수 있었다. 주어진 문제를 그대로 코드로 풀어쓸 필요가 없다는 것도 알게 되었다.
참고
이것이 코딩테스트다 with Python (나동빈 저)
