(JAVA) 백준 15903번 : 카드 합체 놀이

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

11725번: 트리의 부모 찾기

15903번, 카드 합체 놀이

이번 문제는 최소 우선순위 큐를 사용하고 범위를 주의해야 하는 문제이다.

int 가 아닌 Long 을 사용하였는데 이유는 아래에서 설명하겠다.

# Process

main

: x번 카드와 y번 카드 두장을 골라 x+y 의 값으로 x 와 y 번 카드를 덮어쓰는 문제이다.

카드의 수의 최대 값은 1,000,000이다. 모든 최대 경우를 계산했을 때, 1000장의 카드 모두 1,000,000 이고 합체를 15,000번을 진행하게 된다면 int 의 범위를 넘게 되므로 Long 을 사용해야 한다. 필자도 int 를 사용해서 처음에는 틀렸었기 때문에 주의해야 한다.

static void pro() 
{
    while(M-- > 0)
    {
        // 제일 작은 요소 2개를 꺼내서
        long x = q.poll();
        long y = q.poll();

        // 2개 업데이트
        q.add(x+y);
        q.add(x+y);
    }

    long ans = 0;

    for(long k : q)
    {
        ans += k;
    }

    System.out.println(ans);
}

 

위와 같은 풀이를 사용한다면 쉽게 풀 수 있다.

static Long N, M;
// 최소 우선 순위 큐
static PriorityQueue<Long> q = new PriorityQueue<>();

static void input() 
{
    N = scan.nextLong();
    M = scan.nextLong();

    for(int i=1; i<=N; i++) q.add(scan.nextLong());
}

static void pro() 
{
    while(M-- > 0)
    {
        // 제일 작은 요소 2개를 꺼내서
        long x = q.poll();
        long y = q.poll();

        // 2개 업데이트
        q.add(x+y);
        q.add(x+y);
    }

    long ans = 0;

    for(long k : q)
    {
        ans += k;
    }

    System.out.println(ans);
}

 

최소 우선순위 큐를 사용하는 문제가 종종 보여 해당 풀이법을 익히고 최대 우선 순위 큐도 잘 알아두면 추후에 도움이 될 것 같다.

 

// 최소 우선순위 큐
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 최대 우선순위 큐
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

자료구조 Queue 와 Heap 에 대한 공부도 같이 병행하면 좋을 것 같다.

 

 

급하게 조사하고 정리하다보니 부족하거나 틀린 내용이 있을 수도 있는데 댓글로 달아주시면 감사하겠습니다!