[BOJ] 14916 python (기본, dp)

기본 구현

0. -5 가아닌 -2로 하여서 while 문의 if 문 들어가도록

그리고 break

2로 뺐는데 음수 나올 경우도 break

 

n = int(input())

cnt = 0
i = 0
while True:
    if n%5==0:
        cnt += n//5
        break
    else:
        n -= 2 # 5의 배수가 될때까지 <- -5를 하는 것의 역발상 : 이렇게 하면 if 문 다시 타고, 안되면 다시 -2 해주니 ok
        cnt += 1
    
    if n < 0: # 2 로 계속 빼주었는데 음수 나올 경우, 계산 불가 
        break
    
if n < 0:
    print(-1)
else:
    print(cnt)

 

dp 

이 문제가 대표적인 다이나믹 프로그래밍 문제라든데..

문제는 이해 되는데 풀이 과정을 모르겠다 물어봐야 겠다

https://wandukong.tistory.com/15

이 블로그에서 너무 잘 설명되어 있어서 참고하였다. 

코드는 여기

n = int(input())
dp = [-1, -1, 1, -1, 2, 1, 3, 2, 4, 3]
for i in range(10, n+1):
    dp.append(dp[i-5]+1)

print(dp[n])

1. 갯수를 dp테이블에 저장해두는 것이므로 2, 5원을 합한 갯수로저장

2. dp 테이블의 0부터 시작하여 -1 추가함(그 뒤로 1~4 로생각)