[Java] 백준 3661 - 생일 선물

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

3661번: 생일 선물

돈 분배 과정에서 이미 할당량을 채운 객체를 고려해서 메모리 초과가 났던 문제

더 이상 지불할 수 없는 경우를 Array에서 제거하니 통과되었다

 

 

 

[주의할 점]

1. 지불 용이 금액이 높은 사람이 우선순위

-  마지막에 남은 금액을 분배할 때, 지불 용이 금액이 높은 사람을 우선적으로 선택함

- Collections.sort를 이용하여 지불 용이 금액이 높은 사람을 정렬하였음

 

2. 지불한 금액 <= 지불 용이 금액

- 지불 용이 금액을 꽉 채웠을 경우 다음 돈 분배에서 제거함

 

3. 마지막에 순서대로 지불한 금액을 출력

- 우선 지불한 금액은 1차원 int 배열을 이용하여 저장해줌

- Person 클래스 객체를 만들어서 번호(idx), 지불용이금액(limit), 지불한금액(pay) 을 넣어 이용함

- limit==pay인 경우 : 객체를 해당 idx에 pay 값을 넣음 및 Array에서 제거

- 돈 분배가 끝난 후, Array에 남아있는 객체들을 불러와 해당 idx에 pay값을 넣어줌

- int 배열의 각 인덱스 값 출력

 

 

.. 지금 생각해보면 sort는 한 번만 했어도 될거같다.

 

 

[코드]

package BOJ_1000;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class boj3661 {
	static class Person implements Comparable<Person>{
		int idx, limit, pay;
		
		public Person(int idx, int limit, int pay) {
			this.idx = idx;
			this.limit = limit;
			this.pay = pay;
		}

		@Override
		public int compareTo(Person o) {
			return o.limit - this.limit;
		}
	}
	private static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		for(int i=0; i<N; i++) {
			String[] str = br.readLine().split(" ");
			int price = Integer.parseInt(str[0]);
			int n = Integer.parseInt(str[1]);
			
			ArrayList<Person> arr = new ArrayList<>();
			
			str = br.readLine().split(" ");
			for(int j=0; j<n; j++) {
				arr.add(new Person(j, Integer.parseInt(str[j]),0));
			}
			
			int avg = price/n;
			int[] res = new int[n];
			
			for(int j=0; j<arr.size(); j++) {
				Person p = arr.get(j);
				//System.out.println(j);
				if(p.limit <= avg) {
					res[p.idx] = p.limit;
					price -= p.limit;
					arr.remove(p);
					j--;
				}else {
					p.pay = avg;
					price -= avg;
				}
			}
			
			boolean impossible = false;
			while(price>0) {
				
				if(arr.size() == 0) {
					impossible = true;
					break;
				}
				
				// 낼 수 있는 금액이 많은 순서
				Collections.sort(arr);
				
				
				for(int j=0; j<arr.size(); j++) {
					Person p = arr.get(j);
					
					p.pay++;
					price--;
					
					if(p.pay == p.limit) {
						res[p.idx]=p.pay;
						arr.remove(p);
						j--;
					}
						
					if(price==0)
						break;
				}
			}
			
						
			if(impossible) {
				bw.write("IMPOSSIBLE\n");
				continue;
			}
			
			for(Person p : arr) {
				if(res[p.idx]==0)
					res[p.idx] = p.pay;
			}
				
			
			StringBuilder sb = new StringBuilder();
			for(int j=0; j<n; j++)
				sb.append(res[j]+" ");
			
			bw.write(sb.toString().trim()+"\n");
		}
		
		bw.flush();
		bw.close();
	}
}