백준 11399번 ATM

domybest·2021년 4월 10일
0

백준

목록 보기
22/36
post-thumbnail

1번 풀이
2번 풀이
문제

알고리즘

문제 해결은 간단하다. 인출 시간이 가장 짧은 사람 순서대로 정렬하여 시간을 구해나가면 된다. 이 시간을 구해나가는 과정에서 2가지 방법을 생각해 봤다. 메모리 측면에서 1번이 조금 효율적이었지만 별 차이는 없었다.
1번은 수학적 규칙을 이용한 식으로 코딩하는 것이고 2번은 반복적으로 합을 구해나가는 과정이다.
1 2 3으로 정렬 되었다고 하면 각 사람의 대기시간은 1, 1+2, 1+2+3 이다. 이를 모두 더하면 1+1+2+1+2+3이다. 이 때 1은 3번 2는 2번 3은 1번 더해진다. 규칙이 쉽게 보인다. 이를 식으로 만들어 계산한 것이 1번 풀이이다.
2번 풀이는 다음과 같다.

 	int sum = 0;
        int prev = 0;
        for(int i = 0; i < n; i++){
            sum += prev + list[i]; // 1, 1 + 1+2, 1 + 1+2 + 1+2+3 등 총 시간을 저장
            prev += list[i]; // 1, 1+2, 1+2+3 등 각 원소별 대기 시간을 저장
        }

뭔가 코딩적 사고방식에는 2번이 더 잘 맞는 것 같아 2번으로 푸는 것을 선호하여 연습해야 겠다.

profile
기억할 때 까지 반복!

0개의 댓글