SSAFY 합격의 중심, 알고리즘잡스입니다.

성원 감사 CT 퀴즈 이벤트에 참여해주심에 감사드리며,

풀이를 올려주신 야옹 님에게 감사한 마음을 담아, 소정의 상품을 전달드렸습니다.  

앞으로도 많은 참여 부탁드립니다.  

<배수배수 마을> 문제

추후 재업로드 예정

(기존 수강생은 수강생 전용 토론방 참고)

<배수배수 마을> 풀이

배수배수 마을 문제는 그리디 알고리즘을 사용하는 문제입니다.

만약 문제에서 4 7 3 2 4가 주어진다면 마지막 4는 4만큼의 비용을 지불하고 가는게 최선일겁니다. 뒤에 다른 마을이 없으니 최대한 적게 지불하는겁니다.

그 앞 2라는 마을은 뒤에 4를 가야 하므로 2의 배수 중 4보다 크거나 같은 가장 작은 수, 4만큼의 비용을 지불하는게 최선입니다.

그 앞 3이라는 마을은 뒤에 4만큼의 비용을 지불하므로 4보다 크거나 같은 가장 작은 3의 배수, 6만큼의 비용을 지불하는게 최선입니다.

이처럼 뒤에서부터 읽으며 이전 마을에서 지불한 금액보다 크거나 같은 최소 비용을 지불하며 맨 앞까지 간다면 첫 번째 마을에서 지불해야 할 최소 비용을 구할 수 있습니다.

<배수배수 마을> 정답

1) 9

2) 9

3) 18

4) 48

5) 88