백준 카드 합체 놀이(15903)
1. 힌트
1) 합체를 한 번 할때마다 카드는 사라지지 않고 점수는 만큼 늘어납니다.
2) 가장 값이 작은 카드 두 개를 골라서 합치는 것이 무조건 이득입니다.
3) 계산 결과가 32비트 정수형의 범위를 넘을 수 있습니다.
2. 접근
1) 수식으로 표현할 수 있을까?
와 를 골라서 합체하면 수열의 총 합은 어떻게 될까요? 에 쓰여진 값은 로 변하고, 에 쓰여진 값은 로 변합니다. 수식으로 나타내면 이와 같습니다.
수열의 합은 기존에서 만큼 늘어나는 것을 알 수 있습니다.
어떤 카드를 고르더라도 둘 중 어느 카드도 사라지지 않으므로 언제나 가장 작은 것 만을 그리디하게 고르면 점수를 최소화 할 수 있습니다.
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);
}
}
Author And Source
이 문제에 관하여(백준 카드 합체 놀이(15903)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/b15903저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)