[python]Algo-Greedy💢

❓거스름돈 동전구하기

---

<문제>

✅코드

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬로 줄 수 있는 동전 개수
    n %= coin  # 나머지 값을 다음 타켓팅 돈 으로 설정

print(count)

✅문제 접근법

• 가장 큰 수부터 정렬을 해줘야 동전을 최소화로 사용할 수 있다!
• 동전은 사용할때마다 카운트에 누적시킨다
• 동전을 거슬러 주고 남은 돈을 다시 n에 넣어주어 반복할 수 있도록 한다!

❓1이 될때까지

<문제>

<예시>

위에 예시 보면 알듯이 25를 3을 이용하여 1을 만들때 횟수의 최솟값을 출력해야 한다.

✅코드

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

result = 0
 while True:
    #N이 K로 나누어 떨어지는 수가 될때까지 빼기
    target = (n//k) * k
    result +=(n - target)
    n = target

    if n < k:
        break

    result += 1
    n // = k

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

✅문제 접근법:

• 주어진N에 대하여 최대한 많이 나누기를 수행
• N의 값을 줄일 대 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 잇음

02984 -> (0 + 2 * 9 * 8 * 4) 곱하기 혹은 더하기

문제

---

✅코드

 data = input()
 result = int(data[0])

 for i in range (1, len(data)):
     num = int(data[i])
     if result <= 1 or num <= 1 : #계산하는 값 중 둘중 하나라도 0이나 1과 같으면 곱해준다
         result += num
     else:       # 0이나 1일 경우 더해준다
         result *= num
 print(result)

✅문제 접근법

• 앞에 있는 값이 0이나 1이 아닐경우 무조건 곱해주는것이 좋다!
• 0이나 1일경우 곱하게 되면 손해를 보는 형식이므로 더하기를 해준다

참고자료 출처 *https://www.youtube.com/watch?v=2zjoKjt97vQ&t=925s *