문제
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.
- 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
출력
- 첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
예시
| 입력 | 출력 |
|---|---|
| 5 3 1 4 3 2 | 32 |
풀이
이 문제는 최소합을 구하는 문제로 오름차순 정렬을 하여 간단하게 해결 가능하다. 정렬을 하기 위해서 자료구조 List가 필요하다.
이 풀이 방식에는 정렬에 필요한 O(NlogN), 합을 구하기 위한 O(N) 시간 복잡도가 존재한다. 결과적으로 이 풀이 방법은 O(NlogN)의 시간 복잡도를 가진다.
이슈
이번에는 문제의 난이도를 낮추고 대신 알고리즘 순서도를 작성하는 방식을 적용해 보았다. 순서도를 작성하며 내가 문제를 풀이할 때 어떤 점이 부족한지 조금 더 자세하게 알게 되었다.
첫번째로 미리 변수를 선언해보면서 깨닫게 된 점은 문제에서 주어지는 입력 조건과 출력 조건을 보지 않았다는 것이다. 이로 인해 순서도를 작성하다가 입력 받아야 할 포멧이 어떻게 되는지 몰라서 입력 조건을 다시 보고 추가로 순서도에 필요한 변수를 추가로 작성했다는 점이다.
두번째로는 순서도를 작성해야 한다는 생각에 빠져 정작 중요한 합을 구하는 방식을 어떻게 처리할 것인지에 대한 고민을 빼먹었다는 것이다. 단순히 더했던 값에 현재 값을 더해주면 되겠지라고 생각해버린 것이다.
이 두가지 문제점을 종합하면 크게 어떻게 접근할지까지는 생각을 하는데 디테일한 내용까지는 이미 알고 있다라고 착각해버리고 넘긴다는 것이다.
- 문제를 정확하게 읽고
- 입출력 조건을 정확하게 파악하고
- 내가 작성할 알고리즘을 명확하게 정의하자
코드
