3. 그리디

그리디 알고리즘

탐욕 알고리즘. 현재 상황에서 가장 좋은 것만 고르는 방법
정당성 분석을 동반해야 한다. 즉, 단순히 가장 좋아보이는 방법을 선택해도 문제가 풀리는지 파악할 수 있어야 함!!

1. 큰 수의 법칙

문제: 배열의 크기 N, 숫자가 더해지는 횟수 M, 같은 수 연속 가능 횟수 N을 입력받고 가장 큰 수를 계산하기

• 같은 수라도 중복 입력되는 다른 것으로 간주

(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:
  for i in range(k): #가장 큰 수를 k번 연속으로 더함
    if m == 0 :      #m이 0이면 반복문 탈
      break
    result += first
    m -= 1        
  if m==0 :          #m이 0이면 while문 탈출
    break
  result += second   #두 번째로 큰 수를 한 번 더함
  m -= 1

print(result)

(2)수열 활용하기

앞 방법은 n,m,k의 범위가 커지면 런타임에러 가능성이 다분함
반복적으로 더해지는 수열을 발견해서 처리하기

• (k+1)만큼의 수열이 반복됨. 수열 안은 가장 큰 수 k번, 두번째로 큰 수 1번으로 구성
• 가장 큰 수가 더해지는 횟수를 변수 count로 계산

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

data.sort()
first = data[n-1]
second = data[n-2]

#가장 큰 수가 더해지는 횟수
count = (m // (k+1)) * k
count += m%(k+1)

result = first * count 
result += second * (m-count)

print(result)

2. 숫자 카드 게임

핵심: 각 행마다 가장 작은 수를 찾고 그 가운데 가장 큰수를 구하기(그리디)

• 최솟값을 따로 리스트에 저장하고, 리스트의 최댓값을 구하는 방법을 생각함.
  But 해설은 행을 돌면서 동시에 최솟값 중 max값을 바로 result에 저장함
• 리스트의 최솟값을 구할 때: min(list) 사용

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

for i in range(n):   #행의 개수만큼 반복
  data = map(int, input().split()) #열을 입력받기
  min_value = min(data)            #열의 최솟값 찾기
  result = 0
  result = max(result, min_value) #최솟값 가운데 최댓값을 result에 저장

print(result)

3. 1이 될 때까지

핵심: 무조건 많이 나누는게 계산횟수를 줄이는 방법
정당성 확인: 뺼셈보다 나눗셈이 숫자를 큰 폭으로 줄임

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

while n >= k:  #n이 k와 같을 때도 나눠주기
  if n%k != 0: #n이 k의 배수가 아니면 1 뺴기
    n-=1
    result+=1
  n //= k
  result+=1

while n > 1:  #n이 1이 되기 전까지(1보다 클 때)
  n -= 1
  result += 1

print(result)