[이코테 - 그리디 알고리즘] 큰 수의 법칙

이것이 취업을 위한 코딩테스트다 with 파이썬이라는 책이 있다. 유튜버 나동빈님이 쓰신 책이다. 이 책에는 큰 수의 법칙이라는 문제가 나오는데, 이 문제는 그리디 알고리즘으로 푸는 문제이다.

 

문제 설명

N개의 자연수로 이루어진 배열이 입력되었을 때, 배열의 수들을 이용하여 M번 더하여 가장 큰 수를 만들어야 한다. 단, 배열의 특정한 인덱스에 해당하는 수가 K번을 초과하여 연속으로 더해질 수 없고, 인덱스가 다른 경우 수가 같더라도 서로 다른 수로 간주한다.

 

문제 해결 아이디어 

"K번을 초과하여 연속으로 더해질 수 없다"는 문구와 "인덱스가 다른 경우 수가 같더라도 서로 다른 수로 간주한다"는 문구에 주목을 해서 알고리즘을 설계했다. K번을 초과하여 더해질 수 없다는 말은 배열에서 가장 큰 수가 K번까지는 연속으로 더해질 수 있다는 말이다. 그 이후에는 2번째로 큰 수 혹은 (인덱스가 다른 가장 큰 수가 존재할 경우 인덱스가 다른 가장 큰 수) 입력되고, 다시 가장 큰 수로 K번을 연속으로 더할 수 있다는 말이다. 이 점에 초점을 맞추어서 알고리즘을 설계했고, 코딩을 했다.

 

내가 푼 소스코드

n, m, k = map(int, input().split())

array = []
array = list(map(int, input().split()))
array.sort(reverse=True)

res = 0
chk = 0
cnt = 0
for i in range(m):
    if cnt == k:
        cnt = 0
        res +=  array[1]
        continue
    res += array[0]
    cnt+=1
print(res)

[입력]

5 8 3

2 4 5 4 6

[출력]

46

 

5개의 정수로 이루어진 배열을 입력받고, 8번 더하면서 3번 이상 연속으로 나오면 안된다. 내가 설계한 알고리즘대로면 실행하면 6+6+6+5+6+6+6+5가 되어 46이 된다.

 

문제를 풀면서 어려웠던 점

나는 원래 파이썬에 익숙한 사람이 아니다. 그래서 여기서 어려웠던 점은 알고리즘 설계보다는 입력을 받는 부분이었다. 헷갈리지 않도록 복기하는 차원에서 적어두겠다.

n, m, k = map(int, input().split()) # 띄어쓰기로 정수형 3개 입력받기
array = list(map(int, input().split())) # 띄어쓰기로 배열(리스트) 입력받기

# 아래는 2차원 배열(리스트) 띄어쓰기로 입력받는 방법이다.
N = int(input())
array2 = []
for i in range(N):
    array2.append(map(int,input().split()))

책의 문제 풀이 방법

당연하게도 나와 책의 문제풀이 방법은 다르다. 책의 문제풀이 방법은 저작권을 준수하기 위해서 적지 않고, 깃허브로 대체하도록 하겠다.

 

# 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) # 최종 답안 출력

 

책의 문제풀이 방법은 두 가지가 있는데, 점화식을 사용해 더해지는 횟수를 구해서 반복문을 사용하지 않고 문제를 푼 방법이 이코테 깃허브에 있다. 책에는 나처럼 반복문을 사용해 단순하게 푼 방식도 있긴 했다. 아무튼 이런식으로 성능까지 챙긴 것을 보니 나는 아직 부족하다는 것을 느꼈다...