[baekjoon] 2839 자바스크립트 문제풀이 - morethanmin

[utterances-bot]

[baekjoon] 2839 자바스크립트 문제풀이 - morethanmin

알고리즘 문제풀이

https://morethanmin.web.app/archive/algorithm/baekjoon-2839-javascript/

[nahwasa]

5kg 봉지를 최대한 많이 사용하는게 최선이고, 정확히 n kg이 되야 하므로 x=n/5 라고 할 때 x를 0까지 감소시키면서 n-x*5가 3으로 나누어 떨어지는 지점을 찾으면 해당 위치가 최선임다(greedy). 그럼 O(N^2)에서 O(N)으로 복잡도를 줄일 수 있어서 좀 더 효율적으로 가능해요. 이 문제에서는 N이 5000까지라 모든 경우를 다 봐도 되는데, 다른 비슷한 문제에서 n이 최대 5억정도였다면 이 방법으로 풀 수 있게 되니 한번 남겨봐요!