boj 14916 : 거스름돈

문제 주소: https://www.acmicpc.net/problem/14916

난이도: silver 5

1.문제설명

• 2원, 5원 동전으로 거스름 돈을 줄텐데 거스름돈의 동전 수를 최소로 할때의 개수를 구하여라

2.문제해결 아이디어.

• DP로 풀어보자
• 최적화 하고싶은 것은 거스름돈의 갯수 (거스름돈의 갯수를 minimize 하는 것)

3.문제접근법

입력을 받고, 최소값으로 최적화 시킬 것이기 때문에 inf를 설정해준다
그다음 dp테이블을 만들어준다 0번인덱스는 0값이 사실 입력으로 들어오지 않지만
계산의 편의성을 위해 만들어주자.

n = int(input())
INF = float("inf")
dp = [INF] * (n + 1)
coins = [2, 5]

점화식은 다음과 같다.
반복문을 통해 코인에 대해서 다음과같은 식을 정하고 coin부터 n까지 점화한다.

dp[i] = min(dp[i - coin] + dp[coin], dp[i])

4.특별히 참고할 사항

• 딱히 없음
• 일반적인 dp문제이고 사실 dp를 사용하지 않고 greedy한 방법으로 풀 수 있었다.
• 알고리즘을 하나도 모르는 후배한테 풀려봤는데 그 친구는 greedy한 방법으로 풀었다
• 특정 유형에 집착하지 말자

5.코드구현

• dp를 이용한 코드입니다.

n = int(input())
INF = float("inf")
dp = [INF] * (n + 1)
coins = [2, 5]

def get_min_chagne(n):
    if n == 1:# 1이면 종료
        return -1
    elif n <= 4: #4보다 작으면 2원짜리만을 이용해야한다. 
        for coin in [2]:
            dp[coin] = 1
        for coin in [2]:
            for i in range(coin, n + 1):
                dp[i] = min(dp[i - coin] + dp[coin], dp[i])

    else:
        for coin in coins: #5원부터는 2원 5원 모두 사용한다
            dp[coin] = 1
        for coin in coins:
            for i in range(coin, n + 1):
                dp[i] = min(dp[i - coin] + dp[coin], dp[i])

    if dp[n] != INF:
        return dp[n]
    else:
        return -1


print(get_min_chagne(n))

• greedy한 코드

n = int(input())

ans = 0
num = n%5 #입력받은 수를 일단 5로 나눠서 나머지를 구한다
if n == 1 or n == 3: #나머지가 1이나 3이면 -1출력
    print(-1)
    exit(0)

elif num%2 == 0: #나머지가 2라면 n을 5로나눈 몫 + 그 나머지를 2로나눈 몫을 더해서 출력
    print(n//5 + num//2)

else: #나머지가 2로 안나눠진다? -> 5의 몫을 1만큼 줄이고, 그 나머지를 2로 나눠서 출력
    #이 부분이 나름 센스있는게 2로 안나눠진다? -> 이말은 즉 홀수라는 뜻
    #여기에 5를 더해버리면 짝수가되고 2로 무조건 나눠짐
    print((n//5)-1 + (num+5)//2)
    exit(0)