문제
(앞부분 생략)
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
(예시 생략)
배열의 크기 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번을 주목하라. 이는 곧, 배열에서 제일 큰 수와 그 다음으로 큰 수만을 사용해도 된다는 점을 암시하고 있다.
하지만 배열의 갯수가 1개이면 문제가 발생할 수도 있다. 허나 문제의 조건에서 N은 무조건 2보다 크거나 같으므로, 이러한 문제는 발생하지 않는다.
따라서, 가장 큰 값을 연속해서 K번 더하면서, 몇 번 더하는지 count 변수를 이용하여 관측한다. K번을 초과하게 되면, 두 번째로 큰 값을 더해주고 count를 초기화 시켜준다.
풀이
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
answer = 0
max_arr = [arr[len(arr)-1], arr[len(arr)-2]]
count = 0
for i in range(m):
if count >= k:
answer += max_arr[1]
count = 0
continue
answer += max_arr[0]
count += 1
print(answer)
먼저, 배열을 정렬 시켜준다. 문제에서 '특정 인덱스에 해당하는 수'라는 말이 있었지만, 따로 특정 인덱스에 대한 정보는 요구하지 않았으므로, 파이썬에서 제공하는 sort() 를 이용하여 배열을 정렬해준다.
반복문을 M번 돌면서, 아이디어에서 설명하였듯이 시작 전 count 값을 관찰한다. 이후, 만약 가장 큰 수를 K번 더하면, 두 번째로 큰 값을 더하고 count를 초기화 시킨다.
피드백
먼저, 문제를 소홀히 읽은 탓에 총 3번의 시행착오(삽질)을 겪었다.
첫 번째 코드는 어떻게 짰냐면, 제일 큰수 K번 -> 그 다음 큰수 K번 -> 그 다다음 큰수 K번 식으로 코드를 구성했다. 단순하게 생각해서 발생한 문제라고 생각한다.
그 다음 코드는 제일 큰 수 K번 -> 그 다음 큰수 K번 -> 제일 큰 수 K번 으로 짜버렸다.. 이것도 생각을 깊게하지 않고, 풀이의 정당성을 검정하지 않아 발생한 문제였다고 생각한다.
책에서는 수열을 이용한 풀이를 하였다. 반복되는 형태를 관찰했더니 일정하게 반복되는 특징이 있었다. 이렇게도 다시 한 번 풀어보자.
간단한 문제임에도 불구하고 소요시간이 31분이나 걸렸다. 시간을 측정한다는 부담감을 가지고 풀었는데 조급함이 생겨 오히려 삽질을 많이 한 것 같다. 조급하지 말고 천천히 풀도록 노력해보자.(돌갈단)
기타
- 소요시간 : 31분
- 파이썬 배열관련 내장함수들은 숙지해둘 것.
