백준 카드 합체 놀이(15903)

카드 합체 놀이

1. 힌트

1) 합체를 한 번 할때마다 카드는 사라지지 않고 점수는 S[x]+S[y]S[x] + S[y]

2) 가장 값이 작은 카드 두 개를 골라서 합치는 것이 무조건 이득입니다.

3) 계산 결과가 32비트 정수형의 범위를 넘을 수 있습니다.

2. 접근

1) 수식으로 표현할 수 있을까?

S[x]S[x]S[y]S[y]를 골라서 합체하면 수열의 총 합은 어떻게 될까요? S[x]S[x]에 쓰여진 값은 S[x]+S[y]S[x] + S[y]

수열의 합은 기존에서 S[x]+S[y]S[x] + S[y]

3. 구현

public class Main {

	public static void main(String[] args) throws IOException {
		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());
		PriorityQueue<Long> pq = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) pq.offer(Long.parseLong(st.nextToken()));
		for (int i = 0; i < M; i++) {
			long t = pq.poll() + pq.poll();
			pq.offer(t); pq.offer(t);
		}
		long sum = 0;
		for (long x : pq) sum += x;
		System.out.println(sum);
	}

}

좋은 웹페이지 즐겨찾기