코딩테스트 with <이코테>, Greedy algorithm

당장 좋은 것만 선택하는 그리디 

1.  동빈이의 큰수의 법칙 

- 떠올려야 할 아이디어 :
    1. 가장 큰 수를 k번 더하고 더할때마다 남은 카운트를 줄인다.  
       k 카운트가 다 차면 두번째 큰수로 넘어가서 한번을 더해주고 다시 큰수를 
       k 만큼 카운트 한다. 이 과정을 m의 남은 카운트가 0이 될때 까지 반복한다. 

    - 입력예시 : 5 8 3
               2 4 5 4 6

    - 출력예시 : 46

# naive solution

# n = 배열의 크기 , m = 숫자가 더해지는 횟수  , k = 최대 반복 수  
n, m, k = map(int,input().split())

# n = 5, m= 8 , k =3

data = list(map(int, input().split()))

data.sort()
first = data[n-1] # 가장 큰 수
second = data[n-2] # 그 다음 큰 수

result = 0

# N = [2,4,5,4,6], 5

while True: 
    for i in range(k): # i = 0,1,2 3번만 하도록 
        if m == 0:
            break
        result += first # + 제일큰수 , result += 6 , += 12 ...
        m -= 1 # 더한횟수-1

        # i = 0 :  result(0) + fisrt(6) = 6, m(8) -1 = 7
        # i = 1 : result(6) + 6 = 12, m(7) -1 = 6
        # i = 2 : result(12) + 6 = 18, m(6) -1 = 5
      
        # 다시 돌아와서 0,1,2 돌리고
    if m == 0: 
        break
    result += second # result (18) + second(5) = 23, 
    m -= 1 # m(5) -1 = 4

        # 다시 돌아와서 second 더해주면 
        # m==0이므로 break loop 
print(result)

책에서 제시된 효율적인 해결법 :  반복되는 수열에 대한 파악! 

# 수열의 길이 = K + 1, M을 수열의 길이로 나눈 몫 = 수열이 반복되는 횟수 

# 수열 반복되는 횟수 * k = 가장 큰 수가 등장하는 횟수 

# 나누어 떨어지지 않는 경우, M을 K+1로 나눈 나머지 만큼이 가장 큰 수가 추가로 더해짐

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

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

count = int(m / (k+1)) * k # 몫 * k만큼 큰수가 더해짐 
count += m % (k+1) # 나머지가 있다면 그 만큼 추가로 더해짐
                   # 나머지가 0이라면 0이 더해지므로 상관없음 

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

print(result)

2.  숫자 카드 게임 

- 게임룰 : n*m 형태로 놓여있는 카드배열에서 가장 큰 숫자를 가진 카드를 뽑기  
         단, 속해있는 행을 먼저 고른후 그 행에서는 가장 작은 카드를 뽑아야  
         한다.  
         즉, 최소값이 가장 큰 행을 뽑도록 프로그래밍 해야한다.

- 입력예시

        3 3  # (n * m)
        3 1 2  # 실제 카드 입력
        4 1 4  
        2 2 2 

- 출력예시
        2

예시 솔루션 

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

result = 0

for i in range(n): # n개의 행만큼 반복
    data = list(map(int, input().split())) # 첫 입력 리스트로 받기 
    
    min_value = min(data) # 입력받은 리스트중 가장 작은 값 찾기 
    
    result = max(result, min_value) # result와 min_value중 작은값 받기

print(result)

2중 반복문 구조를 이용할 수도 있다. 

# 2중 반복문 구조 이용하기 

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

result = 0 

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

print(result)

3.  1이 될 때까지

- 게임룰: 어떠한 수 N이 1이 될 때까지 다음의 두 과정중 선택하여 반복적으로 수행 
         1. N에서 1을 뺸다
         2. 나누어 떨어진다면, N을 K로 나눈다.

- 입력예시:
         23 3 # n k 
- 출력예시: 
         6

내가 풀어본 솔루션 

# 나의 첫 솔루션 

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

# 23 3 

while n >= k: 
    minus = n % k  # 2 
                                                           
    n -= minus # 나머지 만큼 뺀 값으로 n을 update
    count += minus # 나머지 빼준 만큼 count , count +=2 = 2
                                 
    divde_k = n / k # 21 / 3 = 7 
    n = divde_k # n을 7로 update 
    count += 1 # 나눠줬으니 count +=1 = 3 

if n>1: # 3: n=2, k=3 , into loop 
    n -= 1 #3: 2-1 = 1
    count += 1 # count +=1 = 6


print(int(count))

책에서 제시한 효율적인 해결법 

# 효율적인 해결법
n,k = map(int, input().split())
result = 0

# 23 3

while True: # 나누어떨어질때 까지 1 빼기 
    target = (n//k)*k # n과 가까운 k의 가장 큰 배수를 target에 저장 
    result += (n-target) # n에서 target을 뺀 값(나머지)를 카운트  
    n = target # n을 가장 큰 배수로 update
    
    if n < k:
        break
    result += 1
    n //= k

result += (n-1)

print(result)