문제를 요약하면..
입력한 문자 N을 3과 5로 나눌 수 있는 최소의 개수를 구하는 그리디 문제이다.
시도 1. (실패)
코테 그리디 문제 중 가장 기본인 최소 동전의 개수로 거슬러주는 문제가 있다.
그 문제에서 사용했던 방법을 사용했지만..실패..
※실패이유
최소 동전의 개수로 거슬러주는 문제의 경우 항상 나누어 떨어지게 되어있다.
가장 큰 액수의 동전부터 거슬러주고, 차례대로 작은 액수의 동전으로 거슬러주면 반드시 0이 된다.
하지만 이 문제는 좀 더 응용이 필요하다!
__바로 큰 수인 5부터 나눈 후, 그 나머지 값이 3으로 나누어지는 보장이 없다.
또한, 큰수인 5부터 나눈다고 최소의 개수로 묶을 수 없다.
이 2가지가 <최소 동전의 개수로 거슬러주는 문제>와 다른점이다!!__
3의 배수인 것은 3으로만 나누면 되기에 비리 if N%3==0 으로 걸렀지만 안 걸러지는 것이 있다.
예를들어 11의 경우 5부터 나누면 나머지가 1일이라 위 코드대로 하면 최소의 개수로 묶을 수 없다고 나온다.
하지만 11은 5: 1개, 3: 2개로 나누어질 수 있어 3을 반환해야 한다.
시도2. (정답)
시도 3. (정답)
다이나믹 방식으로 풀이도 있기에 참고해보았다.
-해당 위치보다 -3, -5 작은 위치에서 더 작은 값을 가져와 +1 해주는 방식이다.
-배열의 크기를 N+5를 한 이유는 arr[i-5]의 경우 index outof range 오류가 나기 때문이다.
오늘도 개발중인 ppm's Programming Log