[Python] 큰 수의 법칙 (Greedy)

문제설명

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 m번 더하되 배열의 인덱스에 해당하는 수가 연속해서 k번을 초과하지 않고 가장 큰 수를 만드는 법칙을 '큰 수의 법칙' 으로 정의할때, 배열의 크기 n, 숫자가 더해지는 횟수 m, 그리고 k가 주어질 때 큰 수의 법칙에 따른 결과를 출력하시오.

 

입력조건

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

 

문제풀이

우선 가장 먼저 알아채야 할 사항은 가장 큰 수를 k번 만큼 더한다음 이후 두번재 큰수를 한번만 더해주면 다시 첫번째 큰 수를 더해줄 수 있다. 따라서 몇개의 값을 입력받든 첫번째와, 두번째 큰 수만 알면 되고 나머지 수들은 알 필요가 없게 된다.

이를 기준으로 두가지의 방법으로 구할 수 있다.

 

풀이 1

import sys

result = 0

# n, m, k 값 받기
n, m, k = map(int, input("n, m, k값 입력(공백 구분) : ").strip().split())

# n값 만큼의 자연수 입력받기
numbers = list(map(int, input(f"{n}개 만큼의 자연수 입력(공백 구분) : ").strip().split()))

if len(numbers) != n:
    print("{n}개의 값으로만 입력해야 합니다.")
    sys.exit()

# 입력받은 값 정렬 및 큰 값 두개만 따로 변수 선언
numbers.sort()
first = numbers[n - 1]
second = numbers[n - 2]

while True:
    # 가장 큰 수를 통해 k만큼 계속 더하기
    for i in range(k):
        # 더하는 도중 m번을 더하게 되면 멈춤
        if m == 0:
            break

        result += first
        m -= 1

    # k번을 더하고 난 후는 두번째 큰 수를 한번만 더하기
    if m == 0:
        break

    result += second
    m -= 1

 

첫번째 방법은 단순하게 반복문을 통해 구하는 방법이다. 위 설명처럼 가장 큰 수를 k번 만큼 더한 후 두번째 큰 수를 한번 더하고 다시 첫번째 큰 수로 돌아와서 더해주는 방식으로 이를 m번만큼 진행한다.

가장 쉽게 유추할 수 있는 방법이지만 입력조건으로 범위가 정해지지 않게되는 경우라면 큰 수의 경우 시간초과가 발생할 수 있다.

따라서 아래와 같은 방법으로 구해볼 수 도 있다.

 

풀이 2

import sys

result = 0

# n, m, k 값 받기
n, m, k = map(int, input("n, m, k값 입력(공백 구분) : ").strip().split())

# n값 만큼의 자연수 입력받기
numbers = list(map(int, input(f"{n}개 만큼의 자연수 입력(공백 구분) : ").strip().split()))

if len(numbers) != n:
    print("{n}개의 값으로만 입력해야 합니다.")
    sys.exit()

# 입력받은 값 정렬 및 큰 값 두개만 따로 변수 선언
numbers.sort()
first = numbers[n - 1]
second = numbers[n - 2]

# 큰수와 두번째 큰수가 반복되는 횟수 구하기
firstCount = (m // (k+1) * k) + (m % (k+1))
secondCount = m - firstCount

# 결과값 구하기
result += (firstCount * first) + (secondCount * second)

print(result)

두번째 방법은 이 문제 풀이에 존재하는 규칙을 이용하여 푸는 방식이다. 이 문제는 첫번째 큰수를 k번 더한후 두번째 큰 수를 한번 더하는 방식으로 계속 반복되는 규칙을 가지고 있다. 예를들어 첫번째 큰수가 5, 두번재 큰 수가 4, m = 8, k = 3일 경우 5 5 5 4 5 5 5 4 의 순서로 더해지고 이는 [5 5 5 4]의 반복으로 더해지게 된다.

즉, 하나의 배열이 길이는 k + 1개가 되고 이 하나의 배열에 존재하는 큰 수의 갯수는 k개가 된다. 이 규칙을 기준으로 큰수가 나오는 갯수를 구해보면 m 을 k+1 로 나눈 값이 된다. 단, 이는 나머지가 없이 나누어 졌을 경우이다. 만약 m = 10, k = 3일 경우 2의 나머지가 나오게 되므로 이도 고려해 주어야 한다.

반복되는 배열의 큰수 갯수 = m에서 k+1로 나눈 값의 몫, 이후 나머지 값의 갯수 = m에서 k+1 로 나눈 값의 나머지가 되고 이를통해 firstCount와 secondCount를 구할 수 있다.(secondCount 는 m에서 firstCount의 값만 빼면 간단히 구할 수 있다.)

이렇게 하게되면 값이 첫번째 문제풀이 방식에서 우려된 시간초과의 문제는 사라지게 된다.

 

 

출처 : 이것이 코딩 테스트다(나동빈)