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

ex) 거스름돈 500,100,50,10 원

• cf) 그리디 알고리즘을 풀때에는 정당성을 확인하고 적용해야 한다.

→ ex) 500,400,100원 800원 거스름 돈 (적용 불가)

2023/06/24 (토)

이코테

그리디 파트 공부완료 했습니다.

백준

Problem 1)

try 1) X

N = int(input())

# 3kg or 5kg

cnt = 0

# 우선 15의 배수일 경우 5kg로만 가져가도 정당성이 확보된다.
while N >= 15 :
    N -= 15
    cnt += 3
# N의 범위 0 ~ 14 이다.

# 0 은 고려 X
# 1,2,3,4,5,6,7,8,9,10,11,12,13,14

#1,2,4,7 는 만들 수 없다.
#3,5 (한번)
#6,8,10(두번)
#9,11,13(세번)
#12,14  (네번) 

if N == 3 or N == 5:
    cnt += 1
elif N == 8 or N == 10 or N == 6:
    cnt += 2
elif N == 9 or N == 13 or N == 11:
    cnt += 3
elif N == 12 or N == 14:
    cnt += 4
elif N == 0 :
    pass
else:
    cnt = -1

print(cnt)

# 17에서 오류 납니다

15의 경우 3과 5의 공배수 이기 때문에 N에서 15를 얼마나 빼든 정당성이 확보 되는 줄 알았는데 17에서 예외가 발생.. 정당성 확보 X 틀린 알고리즘