이것저것 개발 블로그

"이것이 코딩테스트다" 책 문제 _ greedy 책 문제

문제)

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다. 이때 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더할 수 없다. 입력 조건에 따라 결과를 출력하시오.

입력 조건

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

출력 조건

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

풀이)

greedy 방법을 사용하여 가장 큰 수를 K번 만큼 더하고, 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다.

입력 예시에 따르면 다음과 같다.

6+6+6+5+6+6+6+5 = 46

1. 내가 작성한 코드

N, M, K = map(int, input().split())
n = sorted(list(map(int, input().split())), reverse=True)
answer = 0
count = 1
for i in range(M):
    if count > K:
        answer += n[1]
        count = 1
    else:
        answer += n[0]
        count += 1
print(answer)

첫째 줄 입력인 N, M, K를 input()을 이용하여 받고, 공백 기준으로 구분하므로 split을 사용한다. 이때 map 함수를 이용하여 문자열을 정수로 바꿔준다.

둘째 줄 입력 또한 같은 방법으로 받되 list를 생성하고 내림차순으로 정렬한다. 

count는 몇 번 더해졌는지 확인하기 위한 변수로 1로 설정해준다.

M번 반복하면서 count가 K보다 큰지 확인한다. (count가 0일 경우 K와 같은지 확인하면 됨)

만약 K번 이내라면, 가장 큰 수를 정답에 더해주고, 아닐 경우 두 번째로 큰 수를 더해준 후 count를 다시 1로 설정해준다.

2. 정답 예시

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)

3. 정답 예시2 _ 수열처럼 생각

가장 큰 수를 K번 만큼 더하고, 두 번째로 큰 수를 한 번 더하는 과정을 반복할 때, 규칙이 생긴다.

이 규칙을 수열처럼 생각한다면 효율성을 높일 수 있다.

입력 예시에서, 

6+6+6+5 + 6+6+6+5 = 46

이렇게 노란색 박스 부분이 반복되는 수열임을 생각할 수 있다.

수열의 길이는 '가장 큰 수 K번 + 두번째로 큰 수 1 번 = K+1'이다.

이 수열은 M을 수열의 길이로 나눈 몫(M // (K+1)) 만큼 더해지고, 나머지 부분(M % (K+1))은 가장 큰 수로만 더해주면 된다. 

가장 큰 수를 더하는 횟수: M // (K+1) * K + M % (K+1)

두 번째로 큰 수를 더하는 횟수: M - 가장 큰 수를 더하는 횟수

결과(정답): 위 두 결과를 합한 값

따라서 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 = m //(k+1) * k + m % (k+1)

result = 0
result += count * first
result += (m-count) * second

print(result)