[2020모각코] 5회차 2021.01.20

Greedy Algoalgorithm이란

문제를 해결하는 과정에서 전체에서의 최적이 아닌 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 방식이다.

 

동전수를 최소화 하기 위해선 가장 큰 거스름돈부터 계산하면 된다.

 

거스름돈의 최대값이 500엔이고 500엔에서 100엔 ,50엔 ,10엔 ,5엔 ,1엔 으로 줄어들게 된다.

/5, /2 연산이 반복해서 이루어지고 있으으모 boolean자료형을 이용하여 잔돈의 값을 자동으로 계산해 주었다.

동전의 갯수가 최소가 되기 위해선 가장 큰 잔돈부터 계산하면 동전의 갯수가 최소가 되게 된다. 따라서 가장 큰 잔돈인 500엔부터 계산을 하여 동전의 최소 갯수를 구하였다.

 

최소 비용으로 가기 위해선 현재 도시의 기름 값보다 낮은 도시에서만 기름을 사면 된다

첫번째 도시에서는 무조건 기름을 넣어야 하기 때문에  첫번째 도시의 가격을 기준으로 프로그램을 작성하였다.

현재 기름 가격과 다음 도시의 기름 가격을 비교하여 다음 도시의 가격이 더 싸다면 현재 쓰고 있는 기름은 다음 도시까지 가는데만 사용하면 되므로 그 다음 도시까지 거리를 통해 기름 가격을 계산하고, 기름 가격을 변화시켰다.