💥이코테 실전문제 뽀개기💥

💻 3-2 큰 수의 법칙

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

---

왜 그리디인가?
큰 수를 최대한 많이 선택하므로

---

📌2020/12/30 작성 코드

nmk = list(map(int,input().split()))
numbers = list(map(int,input().split()))
numbers.sort()
numbers.reverse()

bignum = 0
used = 0
big_idx = 0
for i in range(0, nmk[1]):
    # greedy, 가장 큰 수를 가장 많이 사용한다
    
    # 최대 사용 횟수 초과 시
    if used >= nmk[2]:
        big_idx = 1
        used = 0

    else:
        # 현재 big_idx가 최대가 아니라면 다시 최대로 변경
        # used 초기화
        if big_idx != 0:
            big_idx = 0
            used = 0
    
    bignum += numbers[big_idx]
    used += 1

print(bignum)

---

🤓 문제 해설

• 사실은 입력값 중 가장 큰 수와 두 번째로 큰 수만 저장하면 된다...
• 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복

---

🤓 단순하게 푸는 답안 예시

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
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): #가장 큰 수를 k번 더하기
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 1씩 빼기
    
    if m == 0: # m이 0이라면 반복문 탈출
        break
    
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1 # 더할 때마다 1씩 빼기

print(result) # 최종 답안 출력

---

🤓 더 좋은 답안 예시

🔹 왜 더 좋은 답안인가?
M의 크기가 100억 이상이라면 위 답안으로는 시간초과!😵

🔹반복되는 수열에 대해 파악해보자
input이 2 4 5 4 6 이고 m=8, k=3이라면
(6+6+6+5) + (6+6+6+5)
=> 즉, 6 6 6 5 가 반복된다.

• 반복되는 수열의 길이는 K+1
• m // (k+1) -> 수열이 반복되는 횟수 (나누어떨어지지 않는 경우도 고려하자)
• 따라서 가장 큰 수가 더해지는 횟수는 (M//(k+1)) * K + M % (K+1)

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
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) # 최종 답안 출력

---

🤔 리뷰

• n, m, k = map(int, input().split()) 를 이용해 각각의 변수에 빠르게 값을 할당할 수 있었다!
• 가장 큰 수, 그 다음 큰 수만 활용하여 간단히 구현할 수 있었다
• 가장 큰 수가 몇 번 들어갈 수 있는지를 먼저 계산하고 사칙연산으로 값을 도출하는 방법이 있었군
• 가장 큰 수가 k번 들어가고, 그 다음 큰 수가 1번 들어가니까 (k+1)