[Python] 이것이 코딩테스트다 with 파이썬 - 그리디 - 큰 수의 법칙

* 해당 문제 및 해설은 "이것이 코딩 테스트 다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.  

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

---

그리디 알고리즘이란 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다. 
그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

문제 설명 : 그리디 - 큰 수의 법칙

큰 수의 법칙은 다양한 수로 이루어진 배열(N)이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

입력 조건

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

 

출력 조건

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

 

예시

 

입력 예시	출력 예시
5 8 3 2 4 5 4 6	46

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

 

코드 풀이 및 수행 코드

 

1. 간단한 문제이기 때문에, 구현에 신경을 많이 쓴다.

   = K번 만큼 제일 큰 수를 더하고, 한 번 2번째로 큰 수를 더하고, 또 K번 만큼 제일 큰 수를 더하고를 반복한다.

2. 공식(수식, 방정식) 을 생각했을 수도 있다. (필자처럼)

 

 

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]

result = 0

while True:
	# 가장 큰 수를 k번 더하기
	for i in range(k): 
    	# m이 0이라면 반복문 탈출
        	break
        result += first
        m-= 1
     if m ==0:
     	break
     # 두 번째로 큰 수를 한 번 더하기
     result += second 
     m-= 1

print(result)

 

이 문제는 M이 10,000 이하이므로 이 방식으로도 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커진다면, 시간 초과 판정을 받는다. 

 

 

2번 풀이 : 점화식(공식)을 찾기

# N, M, K 를 공백으로 구분하여 입력받기
n, m, k = map(int,input().split())

# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 정렬
fist = 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)

 

 

 

개인적인 생각

사실 문제를 맨 처음 봤을 때, 규칙이 눈에 보였다.
나중에 진행할 DP(동적 프로그래밍) 도 마찬가지 이지만, 점화식을 찾는 다면 손 쉽게 풀 수 있는 문제라고 생각한다.
(사실 난이도가 매우 낮습니다...)

 

오늘의 개발자 명언

 

사장도 버그날 때는 온다.
(출처 : https://freemoa-blog.com/595)