그리디

• 현재 상황에서 가장 좋은 것만 고르는 방법 이다.

거스름돈

• 카운터에서 거스름돈 500원 , 100원 , 50원 , 10원짜리 동전이 무한히 존재 한다.

• 손님에게 거슬러 줘야 할 돈이 N원 일떄 거슬러 줘야 할 동전의 최소 개수를 구하시오.

• 거스름돈은 10의 배수이다.

해결

• 거스름돈 문제에 쉽게 풀수 있는 방법은 가장 큰 금액 부터 리턴 시켜 주면 된다.

• 거스름돈의 시간 복잡도는 $O(K)$ 이다.

n = int(input())

moneys = [500,100,50,10]

answer = 0


for m in moneys:
    answer += n // m
    n = n  % m


print(answer)

큰수의 법칙

• 해당 수들이 주어질떄 주어진 수들을 M 번 더하여 가장 큰 수를 만드는 법칙이다.
• 단 배열의 특정한 인덱스 에 해당 하는 수가 연속 K번 초과하여 더해질 수 없는 특징이 있다.

해결

• 해당 배열의 내림차순으로 정렬
• 가장 큰 수 부터 K번 규칙을 적용하면 된다.
• 이떄 가장 큰 수와 그 다음 수가 같지 않다면 가장 큰수의 K번 더한 다음 다음 수를 한번만 더하고 다시 가장 큰수를 더한다.
• 만약 가장 큰수 와 두번쨰 수가 같다면 번갈아 가면서 K번 규칙을 적용하면된다.

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

nums.sort(reverse=True)
answer = 0
i = 0
count = 0
while count != m:
    if i == 0:
        answer += (nums[i] * k)
        i += 1
        count += k
        continue
    else:
        if nums[i] == nums[i - 1]:
            answer += (nums[i] * k)
            count += k
        else:
            answer += nums[i]
            count += 1
        i -= 1
        continue

print(answer)

숫자 카드 게임

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

해결

• 각 행에서 가장 낮은 숫자를 뽑은 다음 그중에서 가장 큰수를 리턴하는 프로그램을 작성하면 된다.

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

nums = [list(map(int,input().split())) for _ in range(n)]

smalls = []

for num in nums:
    smalls.append(min(num))

print(max(smalls))

1이 될때까지

• 어떠한 수 N 을 1이 될때까지 두 과정중 하나를 반복적으로 수행하려고 한다.
• 첫번쨰는 N에서 1을 뺸다.
• N을 K로 나눈다.

해결

• N이 K로 나누어 떨어지지 않는 다면 1을 뺴는 작업을 먼저 수행한다.
• K로 나누어 떨어지면 나누어서 N을 줄인다.

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

count = 0

while n != 1:
    if n % k != 0:
        count += 1
        n -= 1
        continue

    n = n // k
    count += 1


print(count)

• 100억 이상 큰수는 해당 프로그램 보다 좀더 효율적으로 만들수 있다.

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

while True:
    # 17 4 라면 17 // 4 = 4 * 4 = 16
    target = (n // k) * k  # 1씩 더할 개수를 측정하는 target
    result += (n - target)  # 원래 N에서 - target 을 뺸 만큼이 1의 개수

    n = target  # 1을 뺴고 남은 수

    if n < k:  # k 가 더 높은 경우 break
        break

    result += 1  # K로 나누기 전에 +1
    n //= k  # k로 나누기

# 마지막으로 남은 수에 대하여 1씩 뺴기 
result += (n - 1)
print(result)