Greedy Algoritm 적용문제

큰 수의 법칙

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

예를 들어 순서대로 2,4,5,4,6로 이루어진 배열이 있을 때 M이 8이고 K가 3이라고 가정할때 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 6+6+6+5+6+6+6+5인 45이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 3,4,3,4,3,으로 이루어진 배열이 있고, M이 7이고 K가 2라고 가정하자. 이 때 4는 두번째, 네번째 원소이므로 번갈아 두번씩 더해 4+4+4+4+4+4+4인 28이 도출된다.

문제

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

코드

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)

그렇다면 가장 큰 수가 몇번 더해졌는지 어떻게 알 수 있을까? 큰수는 K번씩 반복되며 그다음 큰수 한번을 더한 K+1의 횟수로 반복되게 된다. 그렇기 때문에 반복 횟수 M을 K+1로 나눠주면 수열이 몇번 들어있는지 알 수 있고, 해당 수열마다 K번씩 있으므로 K를 곱해준다. 또한 M을 K+1로 나눈 나머지 값만큼의 K가 사용된다. 즉 다음의 코드와 같이 구하면 된다.

코드

count = int(m/(k+1)) * k
count += m%(k+1)

#만약 가장 큰 수만 더한다면?
result += (count)*data[n-1]
#만약 두번째로 큰 수만 더한다면?
result += (m-count)*data[n-2]

숫자 카드 게임

숫자 카드 게임은 여러 카드 중 가장 높은 숫자 카드를 뽑는 게임이며 룰은 다음과 같다.

• 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수, M은 열의 개수이다.
• 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
• 그 다음 선택된 행에 포함된 카드들 중 가장 낮은 카드를 뽑아야 한다.
• 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 낮은 숫자가 낮은 카드를 뽑는 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

다음과 같은 형태로 카드가 있다고 하자

문제

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다.(1 =< N,M =< 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이상 10000이하의 자연수이다.

이 문제는 각 행마다 작은 수를 찾은 다음, 그 중에서 가장 큰 수를 찾는 것이다. 그냥 각각의 행을 Sort해서 첫번째 인자들 끼리 비교하면 될 것 같다.

코드

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

result = 0
for i in range(n):
    data = list(map(int,input().split()))
    min_value = min(data)
    result = max(result,min_value)

print(result)

1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

• N에서 1을 뺀다.
• N을 K로 나눈다.

문제

• 첫째 줄에 N(2 =< N =< 100000)과 K(2 =< K =< 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 N은 K보다 크거나 같다.
• 이 때 N이 1이 되는 최소 회수를 구하라.

코드

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

count = 0

while True:
    if n == 1:
        break
    elif (n % k) == 0:
        n //= k
        count += 1
    else :
        n -= 1
        count +=1

print(count)