학교에서 친해진 형이 추천으로 코딩 학원 초,중등부 학원 알바를 하게 되었다.
그 중에 한 학생이 정보 올림피아드 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 ( 복사 받을 메모리 , 복사 할 메모리 , 길이 )
메모리의 값을 복사해주는 함수 !
사이클을 돌리면서 메모리를 기억해야 할 때 사용했다.
쓰는 이유는 배열에 대량의 데이터 들을 복사해야 할 때 일반적으로 루프를 돌며 사용하는거 보다 이 함수를 통해 메모리 효율을 아낄 수 있다.
'알고리즘' 카테고리의 다른 글
[백준] 7569번 토마토 (PYTHON) (0) | 2024.11.19 |
---|---|
[백준] 17609번 회문 / C언어 (0) | 2024.09.20 |
[백준] 1260 DFS와 BFS (그래프 탐색 / C언어 ) (0) | 2024.07.10 |
[백준] 1271번 엄청난 부자 / python (with c) (0) | 2024.05.02 |
[백준]12789번 도키도키 간식드리미 (스택/ C언어 ) (0) | 2024.04.24 |