[백준] 단계별로 풀어보기(단계:16,그리디 알고리즘,JAVA)11399번, ATM

문제 링크

11399번: ATM

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그리드 알고리즘(탐욕 알고리즘)이란 여러 경우를 선택해야할 때 그 상황에 최적의 경우으로 생각하는 것을 반복하여 최종적인 답을 가져오는 방법입니다.

 

이 문제에서는 ATM대기시간을 최소로 하려면 대기시간이 낮은 순으로 ATM을 사용하여야 합니다.

그래서 ATM대기시간을 기준으로 Array.Sort를 사용하여 오름차순으로 정렬하였습니다.

• ATM기다리는 시간을 저장할 배열 time를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 입력값을 띄어쓰기로 나누어 대기시간을 저장하였습니다.
• 오름차순으로 대기시간이 정렬되어있어서 순서대로 들어가면 최소값을 구하는 것으로 Arrays.sort를 사용하여 오름차순으로 정렬하였습니다.
• 대기시간이 최소인 시간을 구하는 함수 ATM을 만들었습니다.
• BufferedWriter을 사용하여 최소값을 출력하였습니다.

• 2중 for문을 사용하여 오름차순으로 정렬된 대기시간을 순으로 ATM을 이용하도록 하였습니다.
• for문이 종료되면 최초값을 반환하도록 하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] time;	//대기시간 저장 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //-------입력값 저장 및 배열 초기화------------
    	int index = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	time = new int[index];
    	for(int i=0;i<index;i++) 
    		time[i] = Integer.parseInt(st.nextToken());
    	
    	Arrays.sort(time);	//배열 오름차순 정렬
    	
    	bw.write(ATM(index) + "\n");		//결과 출력
    	bw.flush();
    	bw.close();
    	br.close();
	}
    //-------대기시간 최소값 구하는 함수-----------
	public static int ATM(int index) {
		int result = time[0];
		for(int i=1;i<index;i++) {
			int temp=0;
			for(int j=0;j<=i;j++)
				temp += time[j];
			result += temp;
		}
		
		return result;
	}
}