이번 문제는 다이나믹 프로그래밍을 활용하여 해결하였다. 우선 메모라이제이션을 위한 dp배열을 만들고 0으로 채워주고 dp[2]=1을 미리 지정해준다. dp[n]이 0인 경우는 업데이트가 안된 경우이므로 이때는 -1을 출력한다.

이번 문제에서 도출한 점화식은 n이 5의 배수일 경우에는 5원으로만 거슬러 주는 것이 동전의 개수가 가장 적으므로dp[n]=n//5이고, 일반적인 경우는 dp[n]=dp[2]+dp[n-2] 이다.

• dp[1]=0
• dp[2]=1
• dp[3]=0
• dp[4]=dp[2]+dp[2]=2
• dp[5]=5//5=1
• dp[6]=dp[2]+dp[4]=1+2=3
• dp[7]=dp[2]+dp[5]=1+1=2

점화식을 코드로 작성하면 다음과 같이 나타낼 수 있다.

dp[2]=1
for i in range(4, n+1):
   if i%5==0:
      dp[i]=i//5
   else:
      dp[i]=dp[2]+dp[i-2]

코드는 다음과 같이 작성하였다.

• n을 입력받는다.
• 동전의 최소 개수를 저장하는 배열 dp를 선언하고 0 n+1개로 채워준다.
• 만약 n이 2보다 크거나 같다면 dp[2]를 1로 정의해준다.
• 4부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 만약 i%5가 0이라면 dp[i]는 i//5로 갱신한다.
  -> 그 외에는 dp[i]는 dp[2]+dp[i-2]로 갱신한다.
• 만약 dp[n]이 0이라면 -1을 출력한다.
• 그 외에는 dp[n]을 출력한다.

Code

n=int(input())
dp=[0]*(n+1)
if n>=2:
    dp[2]=1
for i in range(4, n+1):
    if i%5==0:
        dp[i]=i//5
    else:
        dp[i]=dp[2]+dp[i-2]
if dp[n]==0:
    print(-1)
else:
    print(dp[n])