1.그리디 알고리즘(탐욕법) - (1) 이론 , 문제1, 문제2

해당 자료들은 https://www.youtube.com/watch?v=Mf0pYO8VAZk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81 의 유튜브 자료를 참고하여 포스팅 하였습니다.

 

그리디 알고리즘 이란?

그리디 알고리즘의 대표적인 문제

 

정답:

n = 1260
count =0

array = [500,100,50,10]

for coin in array:
    count += n // coin
    n %= coin

print(count)

 

문제2 

정답 코드

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

result = 0

while True:
    #N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k
    result += (n-target)
    n = target
    #N이 K보다 작을 때(더이상 나눌 수 없을 때) 반복문 탈출
    if n<k:
        break
    #k로 나누기
    n //= k
    result += 1

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

나의 코드

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

result = 0

while True:
    # n >= k 인지 아닌지 검사
    if n>=k:
        if n % k != 0: #n이 k로 나누어 떨어지지 않으면 n에서 1을 뺀다.
            n -= 1
            result += 1
        if n % k == 0: #n이 k로 나누어 떨어지면 나누어준다.
            n //= k
            result +=1
        if n ==1 : break #n==1이라면 반복문 탈출

    # n < k 인지 아닌지 검사
    else:
        if n == 1:
            break  # n==1이라면 반복문 탈출
        while True:
            n -= 1 #n이 k보다 작기 때문에 계속해서 n을 뺀다.
            result +=1
            if n == 1: break

print("result : ",result)