코테 공부- 그리디 알고리즘

1. 거스름돈 세기

#거스름돈 세기: 그리디 알고리즘

n=1260 #현재 남아있는 잔돈, 나누어야 하는 잔돈
count=0

# 큰 단위의 화폐부터 차례대로 확인하는 그리디 알고리즘 적용

coin=[500,100,50,10] #500원, 100원, 50원, 10원

for num in coin: #coin의 각 항목 num에 대하여
  count+=n//num # 해당하는 화폐로 거슬러 줄 수 있는 동전의 갯수를 센다.
  n%=num

print(count)

 

 

2. 큰 수의 법칙 - 일반적인 방법

#큰 수의 법칙

#N,M,K를 공백으로 구분하여 입력받기
n,m,k=map(int,input().split())
#N개의 수를 공백으로 구분하여 입력받기
#여기서 N는 배열의 크기이고, M은 숫자가 더해지는 횟수, K는 연속해서 더해질 수 있는 한계값이다.
data=list(map(int,input().split()))

data.sort() #입력받은 수를 오름차순으로 정렬한다.

first=data[n-1] #가장 큰 수
second=data[n-2] #두 번째로 큰 수

result=0 #result값 초기화

while True:
  for i in range(k): # 가장 큰 수를 K번 더한다.
    if m==0:
     break #m이 0이 되면 반복문을 빠져나간다.
    result+=first
    m-=1
  if m==0:
   break #m이 0이 되면 반복문을 빠져나간다.
  result+=second 
  m-=1

print(result)

 

3. 큰 수의 법칙- 시간복잡도가 적은 방법

 

#큰 수의 법칙
#N,M,K를 공백으로 구분하여 입력받기
#여기서 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] #두 번째로 큰 수

#가장 큰 수가 더해지는 횟수를 계산한다.
count=int(m/(k+1))*k
count+=m%(k+1)

result=0
result+=(count)*first #가장 큰 수를 더한다.
result+=(m-count)*second #두 번째로 큰 수를 더한다.

print(result)

4. 숫자 카드 게임 

#숫자 카드 게임

#N, M을 공백으로 구분하여 입력받기
#여기서 N=행의 개수, M=열의 개수
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)

#숫자 카드 게임

#N, M을 공백으로 구분하여 입력받기
#여기서 N=행의 개수, M=열의 개수
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)

 

5. 1이 될 때까지

#1이 될 때까지
#단순하게 푸는 답안
n,k=map(int,input().split())
result=0

#N이 K이상이라면 K로 계속 나눈다.
while n>=k:
  #N이 K로 나누어 떨어지지 않으면 N에서 1씩 뺀다.
  while n%k!=0:
    n-=1
    result+=1
  #K로 나눈다.
  n//=k
  result+=1

#마지막으로 남은 수에 대하여 1씩 뺀다.
while n>1:
  n-=1
  result+=1

print(result)

#1이 될 때까지
#빠른 답안

#N,K를 공백으로 구분하여 입력받기
n,k=map(int,input().split())
result=0

while True:
  #(N==K로 나누어 떨어지는 수)가 될 때까지 1씩 뺀다.
  count=(n//k)*k
  result+=(n-count)
  n=count
  #N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문을 빠져 나간다.
  if n<k:
    break
  #남은 수를 K로 바로 나눈다.
  result+=1
  n//=k

#마지막으로 남은 수에 대하여 1씩 뺀다.
result+=(n-1)

print(result)