[BOJ 백준] 20303번 : 할로윈의 양아치(C++)

[BOJ 백준] 20303번 : 할로윈의 양아치 (C++)

00. 시작 전

 

재활운동한 지 4일 차.. 문제가 좀 인상적이었어서 블로그로 작성합니다.

 

01. 개요

출처

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

 

문제

입력

출력

예시

 

---

02. 접근 방식

요약

1. 친구 관계가 있는 아이들을 하나의 그룹으로 만들자. (Union-Find)

2. 그룹 정보를 바탕으로 k명의 사탕을 빼앗을 때, 최댓값을 구하자. (DP)

 

풀이

1. 문제 접근 : 그룹화 (Union-Find)

문제를 읽고 가장 먼저 주목한 점은 "한 아이의 사탕을 뺏으면 그 친구들의 사탕도 줄줄이 뺏게 된다"는 조건이었습니다.

친구의 친구까지 모두 연결된다고 해 Union-Find 알고리즘이 생각났습니다.

• 친구 관계인 아이들을 find와 union 연산을 통해 하나의 그룹으로 묶었습니다.
• 그룹화가 완료된 후, 각 그룹별 총 인원수와 사탕의 총합을 별도로 계산하여 데이터화했습니다.

2. 전략 수립 : 배낭 문제 (Knapsack DP)

그룹별 데이터가 준비되니, 이제 제한된 인원(울음소리가 공명되기 직전의 한계치) 내에서 최대의 사탕을 확보해야 하는 "배낭 문제"로 치환할 수 있다고 생각했습니다.

• 아이템 : 각 그룹 (무게 = 인원수, 가치 = 사탕 개수)
• 목표 : 총 인원수가 K명 미만일 때, 사탕 개수의 최댓값 구하기

3. 최적화 : 2차원 배열에서 1차원 배열로

처음에는 dp[뺏은 아이의 수][그룹 인덱스] 형태의 2차원 배열로 접근했습니다.

하지만 매번 모든 상태를 확인하다 보니 시간 초과가 발생했습니다.

(정확히는 전체를 항상 새롭게 계산하다 보니 캐시 효율이 좋지 않습니다.)

이를 해결하기 위해 공간 최적화를 진행했습니다.

• 1차원 배열 활용 : dp[뺏은 아이의 수] 배열 하나만 유지하며 공간 복잡도를 줄였고, 필요한 구간만 갱신하므로 2차원에 비해서 메모리 접근이 매우 좋습니다. 즉, 2차원 배열보다 캐시 효율 차이가 컸습니다. (2차원 배열은 매번 새로운 행에 값을 복사하고 비교하기 때문입니다.)
• 배열 복사 로직 : 현재 그룹의 계산 결과가 다음 계산에 바로 영향을 주어 중복 계산되는 것을 방지하기 위해, 임시 배열에 계산 결과를 담은 뒤 한 그룹의 확인이 끝날 때마다 메인 dp 배열로 복사하는 방식을 사용했습니다.

---

03. 정답 코드

// 골드 2 - 20303번 : 할로윈의 양아치
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 울음 소리가 공명하기 전까지 뺏을 수 있는 최대 사탕 수
// K명 미만으로 사탕을 뺏을 수 있는 최대수

// 1. 그룹으로 묶는다
// 2. 1차원 배열 사용 [뺏은 인원]

// 1 2 3 4 5 6 7  8  9  10
// 9 15 4 4 1 5 19 14 20 5
// 1 2 1 4 2 2 7  7  4  2

// 1 : 2 -> 13
// 2 : 4
// 4 : 2
// 7 : 2

struct Child
{
    int count = 0;
    int total_count = 0;
    int group = 0;
    int child_count = 1;
};

struct Group
{
    int child_count = 0;
    int value = 0;
};

vector<Child> g_childs;
vector<Group> g_groups;
vector<int> g_counts;

int findParent(int x)
{
    if(x == g_childs[x].group)
        return x;

    g_childs[x].group = findParent(g_childs[x].group);
    return g_childs[x].group;
}

bool unionGroup(int x, int y)
{
    int px = findParent(x);
    int py = findParent(y);

    if(px == py)
        return false;

    g_childs[max(px, py)].group = min(px, py);
    g_childs[min(px, py)].child_count += g_childs[max(px, py)].child_count;
    g_childs[min(px, py)].total_count += g_childs[max(px, py)].total_count;
    return true;
}

void initData(const int N, const int M)
{
    g_childs = vector<Child>(N + 1);

    for(int i = 1; i <= N; i++)
    {
        cin >> g_childs[i].count;
        g_childs[i].total_count = g_childs[i].count;
        g_childs[i].group = i;
    }

    for(int i = 0; i < M; i++)
    {
        int left, right;
        cin >> left >> right;

        unionGroup(left, right);
    }

    g_groups.reserve(N+1);
    for(int i = 1; i <= N; i++)
    {
        if(i == g_childs[i].group)
            g_groups.push_back({g_childs[i].child_count, g_childs[i].total_count});
    }
}

void simulate(const int N, const int K)
{
    g_counts = vector<int>(K, 0);
    vector<int> temps = vector<int>(K, 0);

    // 그룹 검사 인덱스
    for(int i = 1; i <= g_groups.size(); i++)
    {
        // 뺏은 사람 수 
        for(int j = 0; j < K; j++)
        {
            int prev_child_count = j - g_groups[i - 1].child_count;
            // 처음 뺏거나 뺏을 때 이전에 뺏은 기록이 있을 때만 가능
            if(prev_child_count >= 0 && (g_counts[prev_child_count] != 0 || prev_child_count == 0))
                temps[j] = max(g_counts[j], g_groups[i - 1].value + g_counts[prev_child_count]);
            // 처음 뺏는게 아닌데 이전 기록이 없으면, 못 뺏음 - 기록 유지
        }

        // 중첩 방지
        g_counts = temps;
    }
}

int getResult(const int K)
{
    int result = 0;

    for(int i = 1; i < K; i++)
    {
        result = max(result, g_counts[i]);
    }

    return result;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 아이들 수 N, 친구 관계 수 M, 공명하는 수 K
    int N, M, K;
    cin >> N >> M >> K;

    initData(N, M);
    simulate(N, K);
    cout << getResult(K) << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!