이것이 코딩 테스트다 - 큰 수의 법칙 파이썬 문제풀이

이것이 코딩 테스트다 - 큰 수의 법칙

 

 

큰 수의 법칙 문제

 

<이것이 코딩 테스트다> 책에 수록된 문제입니다.

 

문제

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

 

출력조건

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

 

 

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

 

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 

 

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소로에 해당하는 4가 번갈아 두 번씩 더하는 것이 가능하다. 결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 인 28이 도출된다.

 

입력예시

5 8 3

2 4 5 4 6

 

출력예시

46

 

문제풀이

  

이 문제는 전형적인 그리디 알고리즘 문제입니다. 문제 해결을 위해 일단 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 됩니다. 연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두번째로 큰 수를 한 번 더하는 연산'을 반복하면 됩니다. 

 

저는 이렇게 문제를 풀었습니다.

 

n,m,k = map(int,input().split()) #첫째줄 입력값
data = list(map(int,input().split())) #둘째줄 입력값
data.sort()	#둘째줄 정렬

first = data[n-1] #입력값 중에서 가장 큰 값
second = data[n-2] #입력값 중에서 두번째로 큰 값

kcnt = k #가장큰수의 반복 횟수 다시 지정
result = 0 #결과값

for i in range(m):
	if kcnt ==0:
    	result += second
        kcnt = k
    else:
    	result += first
        kcnt = kcnt-1

print(result)

 

책은 이런 답안을 제공했습니다.

 

#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) #최종 답안 구하기

 

제 답안의 경우 입력된 수를 for문으로 돌려 그 속에서 가장 큰 값과 두번째 큰 값을 찾아내어 result에 순차적으로 더했습니다. 책은 큰수와 두번째 수의 규칙을 찾아내어 큰수도 두번째 수가 나오는 count를 구하여 최종 값을 만들어냈습니다. 

 

계산 값은 같겠지만 코딩테스트 문제 풀어감에 있어서 책처럼 사고하는 방식이 필요하다 느낀 시간이었습니다.

 

https://economicyoplait.tistory.com/29

코딩테스트 연습 사이트(온라인 저지 사이트) 소개