[알고리즘] 그리디 알고리즘 연습

1. 큰수의 법칙 문제

#큰 수의 법칙

N, M, K = map(int,input().split())
b = list(map(int, input().split()))
a = sorted(b, reverse = True)

sum = 0

while(M > 0):
    for _ in range(K):
        sum += a[0]
        M -=1
    #중간에 M이 0이 될 수도 있는데, 그걸 생각하지 못했다. 여기에 if m == 0: 을 넣어주면 좋을 것 같다.
    sum += a[1]
    M-=1

print(sum)

#큰 수의 법칙을 반복되는 수열에 집중하여 푸는 방법

n,m,k = map(int,input().split())
b = list(map(int,input().split()))
a = sorted(b, reverse = True)

sum = 0
count = int(m/(k+1)) * k + m%(k+1)
sum += count * a[0]
sum += (m - count) * a[1]

print(sum)

#이중반복문을 간단한 수식으로 바꿀 수 있었다.
#"반복되는 수열"의 특징을 이용하여 "가장 큰 수가 수열에서 나오는 횟수"를 구할 수 있었다.
#총 길이를 반복되는 수열의 길이로 나누고 k를 곱한 것과 나머지를 더하면 가장 큰 수가 수열에서 나오는 횟수다.
#수열이 반복되는 경우 이런 식으로 풀 수 있을 것이다.

 

 

2. 숫자 카드 게임

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

#이차원배열을 어떻게 받아올 수 있을까 고민하였다.
#반복문으로 일차원 배열을 받아서 해결할 수 있었다.
#각 배열의 최소값끼리 비교하여 큰 값을 찾는 것을 생각했다.

max = 0
for i in range(n):
    data = list(map(int,input().split()))
    if min(data) > max:
            max = min(data)
            
#max = max(max, min(data))를 통해서 나타낼 수도 있다. 훨씬 짧은 코드다.

print(max)

핵심은 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것이다.

 

 

3. 1이 될 때까지

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

count = 0

while n != 1:
    if n%k == 0:  #맨 처음에 n/k로 해서 안됐다... 바보... %로 해야지 0으로 되는지 알지...
        n = int(n/k)
        count = count + 1
    else:
        n = n - 1
        count = count + 1

print(count)

n이 클수록 k로 나누었을때 줄어드는 양이 더 많다.

 

여기서 중요한 점

최대한 많이 나누어 줘야한다.

최대한 많이 나눠주기 위해서는 n이 k의 배수로 바껴야한다.

바뀌기 위해서는 1을 빼주는 과정을 거친다.

 

그러니깐 예를 들어서 17을 4로 나눠주기 위해서 1을 빼야지 16을 4로 나눠줄 수 있다.

 

원래의 수에서 밑의 과정을 거치면 k의 배수가 되는 것이다.

while n%k != 0
	n-=1
    result+=1

 

윗 코드의 과정을 빠르게 할 수는 없을까?

target = (n // k) * k

result = n - target

n = target

테크닉: 원래의 수 - k의 배수 = 중간에 1을 빼야하는 횟수가 된다.

이를 통해서 빠르게 구할 수 있다.

 

#1이될때까지 테크닉사용한 버전

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

#빼주고 나눠주고를 반복한다.

result = 0

while True:
    #k의 배수가 될때까지 뺴주는 과정을 수식으로 정의했다.
    target = (n//k)*k
    result = result + n - target
    n = target
    #만약에 나누는 수보다 작아진다면 빠져나온다.
    if n < k:
        break
    #나누는 수보다 작지않다면 나눠준다.
    n = n//k
    result = result + 1
    
#나누는 수보다 작아졌으므로 1이 될때까지의 값을 더해준다.
result = result + (n - 1)
print(result)