1.Greedy(탐욕법)

1.그리디

 

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

(단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요)

-> 항상 최적의 해가 나오지 않을 수 있기 때문에 그리디를 사용할 땐 정당성을 분석해야한다.

 

case1. 거스름돈 문제 O(K)

: 화폐의 종류 K 만큼 시간복잡도가 걸린다.

(정당성 : 10, 50 100, 500 중 큰 금액은 작은 금액의 배수이므로 큰 동전부터 거슬러 계산해주면 된다)

case2. 1이 될 때 까지

: 조건(1.N에서 1을 빼거나, 2.N에서 K로 나눌 수 있다(나누어떨어질 경우만)

(정당성 K값이 1보다 클 경우, 나누어 떨어질 경우에 나누기 부터 한다.

case3. 곱하기 혹은 더하기

: 0,1인 경우는 더하기 나머지 숫자와는 곱하기

# 1260원 거슬러 줘야할 때, 최소 동전 갯수 10,50,100,500
# 잔돈 money
money = 1260
# 잔돈 갯수 numOfCoins
numOfCoins = 0
for coin in [500, 100, 50, 10]:
    # 동전별 잔돈 갯수 n
    n = money // coin
    # 잔돈 갯수 계산
    numOfCoins += n
    # 잔돈 뺀 금액
    money -= (n*coin)
    print(f'{coin}원 동전 : {n}개')


print(f'잔돈의 최소 동전 갯수 값: {numOfCoins} 개')

# N 값일 때 -> 1 될 때까지 몇 번 연산해야하는가?
# : 조건(1.N에서 1을 빼거나, 2.N에서 K로 나눌 수 있다(나누어떨어질 경우만)
# (정당성 K값이 1보다 클 경우, 나누어 떨어질 경우에 나누기 부터 한다.

N = 25
K = 3
# N=int(input())
# K=int(input())
# N, K=map(int,input().split())
# 연산횟수 count
count = 0
while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (N//K)*K
    count += (N-target)
    N = target
    if N < K:
        break
    count += 1
    N //= K

print(count-1)

given_val = "02984"

nums = list(map(int, given_val))
# 가장 큰 값 구하기 answer
answer = 0
for i in range(len(nums)):
    num = nums[i]
    if answer == 0:
        answer += num
    else:
        if num == 1 or num == 0:
            answer += num
        else:
            answer *= num
print(answer)