[백준 알고리즘] 11399 ATM 그리디(21.04.25)

 

오랜만에 시작하는 알고리즘 스터디!!!

 

 

사실 이런 코딩 자체가 너무 오랜만이라 조금 무서웠다..ㅎ

기억도 안나는 알고리즘을

더듬어가면서...

.

.

.

 

 

 

 

 

---

 

 

 

이번주 주제는 Greedy !!!!!!!!!

 

가장 좋은? 최적의 알고리즘을 뽑아내는 유형으로,

문제를 잘 파악하는 것이 중요하다!! 

 

 

 

 

 

그래서 오늘의 문제는

 

백준 11399번 ATM 

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

 

문제 사이트 : www.acmicpc.net/problem/11399

11399번: ATM

 

 

---

여기서 핵심 포인트!!!

 

 

- Short Time Job 형식으로 가장 짧은 시간이 걸리는 사람부터 먼저!!!!

 

- Sum을 어떻게 구현할 것인가?

 

---

 

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

import java.util.Scanner;
public class Main {
	
    // Insertion sort
	static int[] sortingTime(int[] time) {
		int minIndex;
		int i, j;
		for (i = 0; i < time.length - 1; i++) {
			minIndex = i;
			for (j = i + 1; j < time.length; j++) 
				if (time[j] < time[minIndex])
					minIndex = j;
			
			int tmp = time[i];
			time[i] = time[minIndex];
			time[minIndex] = tmp;
		}
		return time;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int num;
		int[] time;
		
		Scanner sc = new Scanner(System.in);
		num = sc.nextInt();
		
		time = new int[num];
		for (int i = 0; i< num; i++) {
			time[i] = sc.nextInt();
		}
		
		time = sortingTime(time);
		
        // sum
		int sum = 0;
		for(int i = 0; i< time.length; i++) {
			int k = i;
			while(k>=0) {
				sum += time[k--];
			}
		}
        
        System.out.println(sum);
	}
}

 

주어진 시간 안에 풀기 위해 급하게 풀어서

Clean Code는 아니지만 ....

 

 

 

그래도 어떻게 풀었는 지 설명하자면,

 

• 먼저 Scanner를 통해 입력을 받아온 후,
• int[] 에 해당 입력을 넣어주고 정렬을 해준다!

 

---

 

정렬은 삽입정렬로 해주었다!

Arrays.sort()를 사용해도 좋다!

 

---

 

 

• 반복문 2개를 통해 sum에 값을 더해준다!

(사실.. 반복문 2개를 사용해서 만든 것은 엄청 깔끔한 코드는 아닌 것 같다!)

 

 

 

 

 

 

 

---

 

백준 알고리즘

채점 결과!!!

 

다행히 맞았습니다!!

 

백준 알고리즘 11399 채점 결과

 

 

 

 

 

 

 

 

 

---

 

 

스터디를 하면서 나온 더 좋은 방법들

 

• C/C++의 <Vector>의 사용
• C/C++의 <algorithm> 라이브러리를 사용한 sort()
• Java의 Arrays.sort() 함수 사용
• 반복문 2개 대신 식 list[i]*(n-1) 사용