[백준] 14916번: 거스름돈 - 파이썬/python

https://www.acmicpc.net/problem/14916

14916번: 거스름돈

접근 방식

- 점화식 고민하기 및 경우의 수 나누기 (2로만, 5로만, 조합으로만, 조합불가)

- 수학적 구현 방법 고민

 

코드 풀이

n = int(input())
cnt = 0
while True:
    if n%5 == 0:
        cnt += n//5 # 5로 나누어 떨어질 때까지
        break
    else:
        n -= 2 # 2를 빼주고
        cnt += 1 # cnt 수 += 1
    if n<0: 
        break

if n<0: # 2를 빼주다 음수가 나오는 경우는
    print(-1) # 나누어떨어지지 않는 경우
else:
    print(cnt) # 그 외에는 첫번째 if에서 break로 끝남

2원과 5원만이 제공 가능한 상황에서, 5원을 최대한 많이 활용할수록 전체 동전의 수는 최소가 됩니다. 따라서 5로 나누어떨어지는지 while true: 를 활용해 계속 검사하며 2씩 빼주는 방법을 활용했습니다.

 

오답 이유

원래는 다이나믹 프로그래밍 연습을 위해 아래의 방식대로 코드를 작성하였습니다. 입력 13일때 출력 5, 입력 14일때 출력 4를 만족하였지만, 채점시에는 시간초과가 발생했습니다.

n = int(input())
dp = [-1] * (n+1)

dp[2] = dp[5] = 1
dp[4] = 2

for i in range(6, n+1):
    for j in range(1, (i//5)+1):
        if (i - (5*j))%2 == 0 and (i - (5*j)) != 0: # 나머지가 없이 떨어지는 경우 제외
            dp[i] = dp[(5*j)] + dp[(i - (5*j))]

        elif i%5 == 0: # 5로 나누어떨어지는 경우
            dp[i] = i//5

        elif i%2 == 0: # 2로 나누어떨어지는 경우
            dp[i] = i//2
        
print(dp[n])