#11399 : ATM

풀이방법

사용된 것:

정렬

동적 프로그래밍(DP)

 

2022.02.24

이 문제는 DP를 사용하기에 적합하다.

n번째 사람의 최종 소요시간은 n-1번째 사람의 최종 소요시간에 자신의 개인 소요시간을 더한 것이다.

즉 앞사람의 최종 소요시간을 구하는 것이 뒷사람의 최종 소요시간을 구하는 문제의 부분 과제이다.

 

사람들의 개인 소요시간을 담은 배열을 오름차순으로 정렬한 뒤, DP를 이용해 앞 사람부터 차곡차곡 수를 더해가며 값을 기록해주면 된다.

 

코드

언어(2022.02.24)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static int[] people;
	static StringTokenizer st;
	static int sum;
	
	static int dp(int cur) {
		if(cur == 0) {
			return people[0];
		}
		people[cur] += dp(cur-1);
		return people[cur];
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		people = new int[n];
		//각 사람별 소요시간 읽어오기
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			people[i] = Integer.parseInt(st.nextToken());
		}
		//오름차순으로 정렬
		Arrays.sort(people);
		//각 사람마다 인출에 걸리는 총 시간을 구하기
		dp(people.length -1);
		//합 구하여 출력
		sum = 0;
		for(int i = 0; i<n; i++) {
			sum += people[i];
		}
		System.out.print(sum);
	}

}

 

Java(2022.03.20, 코드 개선 및 E-PPER 제출용 solution 함수 형식)

	public static int solution(int [] time, int n){
		int answer =0;
	
		Arrays.sort(time);
		
		int dp = 0;
		
		for(int i = 0; i<n; i++){
			dp += time[i];
			answer += dp;
		}
		
		return answer;
	}