#include <cstdio> int main() { int n, result=0; for(scanf("%d", &n); ; n-=3, result++) { if(n==0) break; if(n%5==0) { result += n/5; break; } if(n<0) { result = -1; break; } } printf("%d\n", result); return 0; }
계속 다이나믹 프로그래밍 분류만 하다가, 수학부분에서 문제를 한번 풀어보았다. 문제를 찾다가 뭔가 너무 쉬워보여서... 나름대로 정답 비율이 낮은 걸로 찾다가 28%짜리 '설탕배달'을 풀게 되었다.
3키로 5키로 짜리 봉지로 적은 개수의 봉지를 배달할 수 있도록 하는 것인데, 뭐 이런 저런 방법으로 풀 수 있을 것 같다.
풀이 방식은, 3씩 줄이면서, 5로 나누어 떨어지는지 확인하는 것이다. 나름대로 가독성을 고려했기 때문에, 이해하는데 어려움은 없으리라 생각한다.
알고리즘 분류 : 다이나믹 프로그래밍
EmoticonEmoticon