[C++] 백준 11399번 ATM

그리디 알고리즘 문제.

 

그리디 알고리즘이란?

각 단계에서 최선일 것 같은 방법을 선택하는 알고리즘. 어떤 값을 최대화, 최소화하는 문제의 해를 찾는 문제이다. 큰 수 혹은 작은 수부터 각 단계에서 최대한 사용하는 것이다. 매 순간 최선인 방법을 선택하는 알고리즘이지만, 그게 전체적으로 봤을 때 항상 최적의 방법은 아닐 수 있다 !

 

처음 접근 방식

이 문제를 처음 봤을 때는, Pi 이런식으로 설명해서 점화식을 유도하는 문제라고 생각했다.

그래서 DP로 풀려고 했는데 특별하게 보여지는 규칙은 없었고 그냥 최종적으로 총 걸리는 시간을 더할 때

Bottom Up 방식과 비슷하게 더하는 것 뿐이였다.

문제에 두번째 예시를 보면 결국 시간이 적게 걸리는 사람부터 정렬했을 때 최소 시간의 합이 된다.

중간에 다른 조건이 없으므로 결국 정렬을 사용해서 오름차순으로 정렬한 후에 시간이 적게 걸리는 사람부터

차례로 더해나가면 되겠다고 생각했다.

 

문제풀이

 

사용한 STL과 변수

우선 사람마다 몇분이 걸리는지(단순히 걸리는 시간) 저장하기 위해 vector를 사용했고,

최종적으로 사람마다 몇분을 써야하는지(기다리는 시간 + 걸리는 시간)을 저장하기 위해 배열을 하나 만들었다.

n은 사람의 수, result는 결과값 변수이다.

 

메인함수

메인함수에서는 처음에 vector의 0번째 공간은 사용하지 않기 위해 0을 삽입했다.

그리고 사람의 수만큼 걸리는 시간을 입력받고

sort 메서드를 이용해서 정렬해준다.

그리고 반복문을 이용해서 현재 사람이 인출하는데 걸리는 시간 + 이전 사람이 총 걸리는 시간 = 현 재사람이 걸리는 총 시간(An = A(n-1) + Pn)임을 이용해서 저장하고 result 변수에 하나씩 차례로 더해나간다.

그리고 result 값을 출력한다.

 

어떻게 접근해도 그리디 알고리즘을 유추해낼 수 있다고 생각한다.

어려운 문제는 아니였다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.