📖문제
'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다.
동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 그리고 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
입력 조건
- 첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.
단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
- 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.
📝풀이과정
- 크기가 N인 배열을 입력받고 가장 먼저 그 배열을 내림차순으로 정렬한다.
- 배열에서 가장 큰 수와 그 다음으로 큰 수를 알아낸다.
- 가장 큰 수를 연속하여 K번 더한다.
- 두 번째로 큰 수를 한 번 더한다.
- 더하는 과정이 M번이 될 때까지 1번, 2번 단계를 반복한다.
⌨코드1
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
# 배열 내림차순으로 정렬하기
arr.sort(reverse = True)
answer = 0
while True:
# 1. 가장 큰 수를 연속하여 K번 더한다.
for i in range(k):
# 더하는 과정이 M번이 되면 반복문 탈출
if m == 0:
break
answer += arr[0]
m -= 1
# 더하는 과정이 M번이 되면 반복문 탈출
if m == 0:
break
# 2. 두 번째로 큰 수를 한 번 더한다.
answer += arr[1]
m -= 1
print(answer)📖문제 변형
- 만약 M이 100억을 넘긴다면, 연산의 횟수가 100억을 넘어가기 때문에 제한시간 안에 정답을 도출하지 못할 수 있다.
- M이 100억을 넘긴다고 가정하고, 위의 코드보다 답을 더 빠르게 구할 수 있는 방법을 생각해보자.
📝풀이과정
- M과 K가 주어지면 배열에서 가장 큰 수와 두 번째로 큰 수가 각각 얼마나 더해져야 큰 수를 만들 수 있는지 정해진다.
- 가장 큰 수와 두 번째로 큰 수가 더해질 때 더해지는 순서는 수열의 형태로 반복되면서 더해진다. 그리고 이 수열의 크기는 (K + 1)이다.
- 이 수열이 반복되는 횟수는 M // (K + 1)이 되고, 이것을 count라고 표현하기로 하자.
- 그리고 만약 M / (K + 1)이 나누어 떨어지는 수가 아니라면 가장 큰 수를 나머지만큼 더 더해줘야 한다.
- 결국 가장 큰 수가 더해지는 횟수는 count * K + M % (K + 1),
두 번째로 큰 수가 더해지는 횟수는 count가 된다.
⌨코드2
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
# 배열 내림차순으로 정렬하기
arr.sort(reverse = True)
# 수열이 반복되는 횟수 count
count = m // (k + 1)
# 가장 큰 수가 더해지는 횟수
first_cnt = k * count + m % (k + 1)
# 두 번째로 큰 수가 더해지는 횟수
second_cnt = count
answer = arr[0] * first_cnt + arr[1] * second_cnt
print(answer)
☺ 느낀점
두 번째 풀이는 '이것이 코딩 테스트다' 책에서 알려줘서 생각할 수 있었다.
코딩테스트 문제를 풀 때는 시간복잡도와 공간복잡도를 같이 생각해야 한다는 것을 항상 염두에 두고 문제를 풀자 :)
아 그리고 아직 파이썬 문법이 손에 익지 않아서 list를 입력 받는 것부터 어떻게 해야할지 막막했었다...파이썬 문법을 다시 공부해야겠다...^0^
할 수 있어! :)