그리디_알고리즘

[C++] 백준 11399번 ATM

그리디 알고리즘 문제. 그리디 알고리즘이란? 각 단계에서 최선일 것 같은 방법을 선택하는 알고리즘. 어떤 값을 최대화, 최소화하는 문제의 해를 찾는 문제이다. 큰 수 혹은 작은 수부터 각 단계에서 최대한 사용하는 것이다. 매 순간 최선인 방법을 선택하는 알고리즘이지만, 그게 전체적으로 봤을 때 항상 최적의 방법은 아닐 수 있다 ! 처음 접근 방식 이 문제를 처음 봤을 때는, Pi 이런식으로 설명해서 점화식을 유도하는 문제라고 생각했다. 그래서 DP로 풀려고 했는데 특별하게 보여지는 규칙은 없었고 그냥 최종적으로 총 걸리는 시간을 더할 때 Bottom Up 방식과 비슷하게 더하는 것 뿐이였다. 문제에 두번째 예시를 보면 결국 시간이 적게 걸리는 사람부터 정렬했을 때 최소 시간의 합이 된다. 중간에 다른 조..