[백준 / 올림피아드 ] 28325번 호숫가의 개미굴 ( DP , greedy / c언어)

학교에서 친해진 형이 추천으로 코딩 학원 초,중등부 학원 알바를 하게 되었다.

 

그 중에 한 학생이 정보 올림피아드 1차 예선을 붙어서 2차 준비를 맡게 되었다.

 

중등부 정보 올림피아드 문제를 보는 순간 약간 당황스러웠던 점이 많았다.

 

일단 생각보다 난이도 더 높았다. 

 

특히 시간 복잡도, 공간 복잡도를 하나 하나 체점을 하는 방식이다.

 

총 올림피아드 문제는 4문제로 2문제만 정확히 맞추면 되는 목적으로 가르치라고 명을 받게 되었다.

 

그 중 2번 문제인 이 문제는 난해한 구현 문제였다.

 

그래서 어떻게 최적의 알고리즘을 짜야할지 고민을 많이 했다. 

 

백준 기준 골드 5의 난이도 DP 문제이다.

 

 

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

 

 

DP(Dynamic Programming)란? 다이나믹 프로그래밍은 그냥 하나의 큰 문제를 작은 문제로 해결하는 방법

 

그 안에서는 재귀와 반복문을 통해 설계하는 방식이 있고 top-down / Bottom-up 방식으로 문제를 해결한다.

 

top-down은 큰 문제를 작은 문제로 바꿔가며 해결하는 방식 !

 

bottom-up은 문제 중에 가장 작은 문제를 해결하며 이를 바탕으로 전체적인 문제를 해결하는 방식 ! 

 

dynamic은 그냥 멋있어 보일려고 붙인 일종에 별명이라고 생각한다.

 

 

이 문제를 해결할 때는 top-down 형식으로 풀어나갔다.

 

함수들을 설정해서 메인함수 진출전에 필요한 메모리 효율성 구조와 알고리즘을 짰다.

 

 

 

-문제

 

개미굴 구하기

 

- 모든 개미굴에 쪽방이 있다면 쪽방의 개수가 답. 

 

- 모든 개미굴에 쪽방이 없다면 3개의 개미굴에 한 마리가 들어갈 수 있다.

 

- 모든 쪽방에 있을수도 없을수도 있는 경우의 수들을 생각.

 

 

이 문제에서 개미굴의 방을 정점으로 두 방 연결하는 통로를 간선으로 생각을 한다.

 

즉 정점에 대한 사이클과 그 사이클에 대한 정점이 가지고 있는 또 다른 정점을 생각하는 방식으로 문제를 해결했다.

- 회전하는 형식을 그렸다.

 

일단 처음은 개미의 최댓값을 구하는게 목적 !

 

그래서 그 최댓값을 출력한다.

 

사이클을 돌리기 전에 빈방이 있는지 없는지를 확인을 파악도 해야한다.

 

그래서 빈 방의 개수 + 1 / 2 를 해서 더 해주는 알고리즘을 짜야한다.

 

짝수 번째 정점에 대해서 개미를 하나씩 배치하게 되면 (정점/2)마리의 개미를 배치 하고 이보다 더 많이 배치 할 순 없다.

 

이제 정점에 관점에 대해 생각을 완료했다. 

 

그럼 이제 연결된 간선에 대해서 생각을 해봐야 한다. 

 

사이클을 구성하면서 간선이 하나라도 끊어지면 이 그래프는 트리로 바뀌는 것을 알아야한다.

 

그래서 이 사이클을 구성할 때 간선은 ( i , i+1 ) 이 되는점을 생각한다.

 

 

그럼 경우의 수가 4가지가 나온다.

 

1. 한 정점과 그 나머지 자손 정점만 남긴 채, 그 정점과 n번째 정점도 선택하지 않은 최댓값.

 

2. 한 정점과 그 나머지 자손 정점만 남긴 채, 그 정점을 선택하고 N번째 정점을 선택하지 않은 최댓값.

 

3. 한 정점과 그 나머지 자손 정점만 남긴 채, 그 정점을 선택하지 않은 최댓값

 

4. 한 정점과 그 나머지 자손 정점만 남긴 채, 그 정점을 선택한 최댓값.

 

 

 

 

 

- 전체 코드 ( c언어 )

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long ll;

ll N, A[252525], C[252525], R;

int compare(const void *a, const void *b) {
    return (*(ll*)a - *(ll*)b);
}

ll max_element_index(ll *arr, ll size) {
    ll max_idx = 0;
    for (ll i = 1; i < size; i++) {
        if (arr[i] > arr[max_idx]) {
            max_idx = i;
        }
    }
    return max_idx;
}

void rotate(ll *arr, ll first, ll n) {
    ll *temp = (ll*)malloc(n * sizeof(ll));
    memcpy(temp, arr + first, (n - first) * sizeof(ll));
    memcpy(temp + (n - first), arr, first * sizeof(ll));
    memcpy(arr, temp, n * sizeof(ll));
    free(temp);
}

ll count(ll *arr, ll size, ll value) {
    ll cnt = 0;
    for (ll i = 0; i < size; i++) {
        if (arr[i] == value) {
            cnt++;
        }
    }
    return cnt;
}

ll accumulate(ll *arr, ll size) {
    ll sum = 0;
    for (ll i = 0; i < size; i++) {
        sum += arr[i];
    }
    return sum;
}

int main() {
    scanf("%lld", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
    }
    if (count(A + 1, N, 0) == N) { 
        printf("%lld", N / 2); 
        return 0;  
    }
    ll max_idx = max_element_index(A + 1, N);
    rotate(A + 1, max_idx, N);
    R += accumulate(A + 1, N);
    for (int i = 1, j; i <= N; i++) {
        if (A[i] || C[i]) continue;
        for (j = i; j <= N && !A[j]; j++) C[j] = 1;
        R += (j - i + 1) / 2;
    }
    printf("%lld", R);
    return 0;
}

 

 

새롭게 알게된 점

 

memcpy ( 복사 받을 메모리 , 복사 할 메모리 , 길이 )

 

메모리의 값을 복사해주는 함수 !

 

사이클을 돌리면서 메모리를 기억해야 할 때 사용했다.

 

쓰는 이유는 배열에 대량의 데이터 들을 복사해야 할 때 일반적으로 루프를 돌며 사용하는거 보다 이 함수를 통해 메모리 효율을 아낄 수 있다.