[백준] 23889 : 돌 굴러가유 - JAVA

문제

https://www.acmicpc.net/problem/23889

23889번: 돌 굴러가유

 

풀이

그리디 문제

 

돌은 오른쪽으로 굴러간다.

그렇다면 돌이 굴러가기 시작하는 위치부터 막는다면 더 많은 피해를 막을 수 있다.

따라서 돌이 굴러가기 시작하는 위치부터 그다음 돌이 굴러가는 위치 까지의 합이 가장 큰것부터 내림차순으로 정렬해주면 된다.

 

코드

import java.io.*;
import java.util.*;

class Main {	
	
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int house [] =new int [n];
		int stone [] = new int [k];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			house[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<k;i++) {	
			stone[i] = Integer.parseInt(st.nextToken());
		}

		List<int []> breakStone = new ArrayList<>();
		
		for(int i = 0; i < k-1; i++) {
			int beforeBreakSum = 0;
			for(int j = stone[i]-1; j<stone[i+1]-1;j++)
				beforeBreakSum += house[j];
			breakStone.add(new int[] {beforeBreakSum, stone[i]});
		}
		int beforeBreakSum = 0;
		for(int i = stone[k-1]-1; i<n;i++)
			beforeBreakSum += house[i];
		breakStone.add(new int[] {beforeBreakSum, stone[k-1]});
		
		
		Collections.sort(breakStone, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
		
//		for(int [] arr : breakStone) {
//			System.out.println(arr[0]+" "+arr[1]);
//		}
//		
		int answer [] = new int [m];
		for(int i=0;i<m;i++) {
			answer[i] = breakStone.get(i)[1];
		}
		
		Arrays.sort(answer);
		
		for(int i=0;i<m;i++) {
			System.out.println(answer[i]);
		}
		
		
	}
	
}