[Disjoint Set] BOJ 25579 터트려라 풍선

문제

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

25579번: 터트려라 풍선

 

 

접근 방법

• 일반적으로 생각했을 때 떠오르는 방법인 각 풍선을 하나씩 터트린다는 방법으로 점수계산을 수행하면 구현이 매우 빡세진다. 구간이 계속해서 변동되고, 합과 결과도 계속 관리해주어야 하기 때문이다.
• 따라서 이를 역으로 생각해보자. 모두 터져있는 상태에서 터트린 순서의 역순으로 풍선이 생성된다고 가정하는 것이다.
• 풍선을 생성시킬 때 마다. 생성시킨 풍선의 양 옆에 다른 풍선이 생성되어 있는가를 확인하고, 존재한다면 segment라는 것이기 때문에 두 풍선을 동일한 segment로 묶어주어야 한다.
  • 만약 양 옆에 어떠한 풍선도 존재하지 않는 상태라면 그 풍선은 그 자체로 하나의 segment라고 할 수 있다.
• 이 segment를 하나의 set으로 생각하자. 그렇다면 만약 풍선의 양 옆에 풍선이 존재한다면 이 두 set을 1개의  set으로 합쳐야 한다는 것이다.(Union) 또한 점수의 계산에서 segment의 길이(크기)를 곱해주어야 하므로 자연스럽게  Union By Rank를 이용하여 segment의 길이를 구할 수 있다.
• 문제는 점수의 총합을 계산하는 것이다. 직전에 합해주었던 값을 빼고, 다시 새롭게 계산된 값을 넣어주어야 한다. 이것은 Union을 하기 직전에 해당 집합에서 계산된 값을 빼주고(총합에선 더해졌기 때문에), 다시 계산한 뒤에 총합에 추가해주면 해결된다.
• 즉, Union-Find 자료구조를 구현하되 조금 커스터마이징하여 각 쿼리에 대해 점수를 계산하는 문제였다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] parents;
    static int[] score;
    static int[] seq;
    static long[] sum;
    static int[] size;
    static long ansSum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        parents = new int[N + 1];
        score = new int[N + 1];
        seq = new int[N + 1];
        sum = new long[N + 1];
        size = new int[N + 1];
        ansSum = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++){
            score[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }

        long ans = 0;

        for (int i = N; i > 1; i--){
            int k = seq[i];

            parents[k] = k;
            sum[k] = score[k];
            size[k] = 1;

            ansSum += sum[k];

            if (k - 1 >= 0 && parents[k - 1] != 0){
                union(k - 1, k);
            }

            if (k + 1 <= N && parents[k + 1] != 0){
                union(k, k + 1);
            }
            
            ans = Math.max(ans, ansSum);
        }
        System.out.println(ans);
    }

    public static void union(int u, int v){
        int pu = find(u);
        int pv = find(v);
        
        ansSum -= sum[pu] * size[pu];
        ansSum -= sum[pv] * size[pv];

        if(size[pu] > size[pv]){
            parents[pv] = pu;
            size[pu] += size[pv];
            sum[pu] += sum[pv];

            ansSum += sum[pu] * size[pu];
        } else{
            parents[pu] = pv;
            size[pv] += size[pu];
            sum[pv] += sum[pu];

            ansSum += sum[pv] * size[pv];
        }
    }

    public static int find(int v){
        if (v == parents[v]){
            return v;
        }

        return parents[v] = find(parents[v]);
    }
}

 

 

여담

• 이 문제는 처음 백준의 Open Contest에 참가했을 때 맞닥드린 문제였는데. 그때는 어떤 방식으로도 접근이 안되어서 좌절했던 기억이 난다.
• 7개월 전이었는데 지금 약간의 힌트를 얻고 구현이 가능해져 실력이 늘었다라는 증명이 되는 문제였다. 역시 꾸준히 하면, 어느 정도의 선까지는 실력은 따라오는 것 같다.