[백준] 14916 거스름돈

J. Hwang·2024년 8월 20일

coding test

목록 보기

14/108

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

내 풀이


def change(n):
    no2 = n//2
    no5 = n//5
    cases = [[x,y] for x in range(no2+1) for y in range(no5+1)]
    cases1 = [a for a in cases if n-a[0]*2-a[1]*5==0]
    if len(cases1) == 0:
        return -1
    else:
        cases2 = [sum(b) for b in cases1]
        return min(cases2)
        
print(change(int(input())))

코멘트

메모리 초과로 장렬하게 실패!
DP 방법으로 풀지 않아서 그런 듯 하다. 내 풀이와 같은 코드로 하면 n이 커짐에 따라 cases가 무한히 많아져서 메모리가 초과되는 듯.

아래 reference에 링크 걸어놓은, DP 배열 만들어서 아주 정석적으로 깔끔하게 푼 풀이를 참고해서 고쳐보았다.

def change(n):
    if n == 1:
        return -1
    elif n == 2:
        return 1
    elif n == 3:
        return -1
    elif n == 4:
        return 2
    else:
        dp = [1000000]*(n+1)   # 0th -> no use
        dp[2] = 1
        dp[4] = 2
        dp[5] = 1
        
        for i in range(5, n+1):
            dp[i] = min(dp[i], dp[i-2]+1, dp[i-5]+1)
            
        if dp[n] == 1000000:
            return -1
        else:
            return dp[i]
    
print(change(int(input())))

⚠️ dp 배열 초기화할 때 수를 크게 설정해야 한다. 입력되는 n 범위가 최대 10만으로 굉장히 크기 때문에. dp = [10000]*(n+1)으로 설정했을 때는 실패가 떴는데 dp = [1000000]*(n+1) 로 설정하니 잘 된다.

추가 코멘트 (241110)

위는 예전에 친구들과 스터디를 할 때 풀었던 문제인데 약 3달 뒤에 항해99 1일 1코테 챌린지로 다시 풀게 되었다. 이미 푼 문제를 배정받아서 스킵할까도 생각했지만 코테를 자주 풀다 보니 복습이 중요하다는 것을 깨닫게 되어...

지금 다시 예전 풀이를 보니 정말 알고리즘에 대해 1도 몰랐구나 싶다. (물론 지금도 잘 모름...) DP 유형이라 이해도 잘 되지 않는 풀이로 고쳐 푼 점도 눈에 띈다. 그래서 그런지 이번에 다시 풀어볼 때에도 DP를 사용하지 않고 그리디로 풀었다. (물론 그리디로 풀어도 문제 없이 잘 되었음) 새로 푼 코드가 한 방에 정답 처리 되는 것을 보니 조금은 늘었나 싶어서 기분이 좋다. 더 열심히 해야지.

import sys
input = sys.stdin.readline

n = int(input())

def change(money):
    if money < 2:
        answer = -1
    elif money == 2:
        answer = 1
    elif money == 3:
        answer = -1
    elif money == 4:
        answer = 2
    elif money == 5:
        answer = 1
    else:    # money >= 6
        result1 = money // 5
        result2 = money - 5*result1
        if result2 % 2 == 0:
            answer = result1 + result2/2
        else:
            while result1 > 0:
                result1 -= 1
                result3 = money - 5*result1
                if result3 %2 == 0:
                    answer = result1 + result3/2
                    break
                else:
                    answer = -1
    return int(answer)            
        
print(change(n))