[백준] 24460 특별상이라도 받고 싶어 - C

 

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

 

---

 

N*N의 배열을 4등분하고, 2*2의 크기가 되면 해당 4개의 원소들을 정렬한 후

2번째로 작은 값을 return한다.

이 일련의 과정을 재귀적으로 구현하면 될 것 같다.

 

#include <stdio.h>

int arr[1025][1025];
int function(int n, int x, int y);
void swap(int* a, int* b);
void quick_sort(int start, int end, int *temp);

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	printf("%d",function(n, 0, 0));
	return 0;
}
int function(int n, int x, int y) {
	int temp[4];
	if (n == 1) {
		return arr[y][x];
	}
	temp[0] = function(n / 2, x + n / 2, y);	
	temp[1] = function(n / 2, x, y);
	temp[2] = function(n / 2, x, y + n / 2);
	temp[3] = function(n / 2, x + n / 2, y + n / 2);
	quick_sort(0, 3, temp);
	return temp[1]; //sec_min
}
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void quick_sort(int start, int end, int *temp) {
	if (start >= end) return;
	int pivot = start;
	int lo = start + 1;
	int hi = end;
	while (lo <= hi) {
		while (temp[lo] <= temp[pivot] && lo <= end) lo++;
		while (temp[hi] >= temp[pivot] && hi > start) hi--;
		if (lo > hi) {
			swap(&temp[hi], &temp[pivot]);
		}
		else {
			swap(&temp[lo], &temp[hi]);
		}
	}
	quick_sort(start, hi - 1, temp);
	quick_sort(hi + 1, end, temp);
}

 

---

코드 설명

• function 함수
• 배열의 크기 N을 받아 N/2로 재귀 호출한다.
• 현재 배열을 제 1,2,3,4분면으로 나눠, return을 각각 temp[0],[1],[2],[3]에 저장한다. (2번째로 작은 값이 return으로 올 것이다.)
• 퀵정렬(quick_sort)을 이용해 값을 오름차순으로 정렬한다. (굳이 퀵정렬이 아니어도 되지만, 개념 이해도 할 겸..)
• 정렬된 값에서 2번째로 작은 값을 return 한다.
• ** temp 배열은 지역으로 선언해야 한다. quick_sort로 값을 넘겨주기 귀찮다고 전역으로 선언하면 재귀호출된 function과 temp 배열을 공유하기 때문에 계산이 올바르게 되지 못한다.
• quick_sort 함수
  • 퀵정렬을 수행하는 함수이다..
• main 함수
  • 입력을 받는다.
  • function을 n,0,0으로 호출한다. (x, y가 0, 0이어야 N이 1로 입력되었을 때 올바른 값을 출력한다.)

---

 

 

아이디어 자체는 간단한 것 같다.

굳이 퀵정렬을 사용할 이유는 없지만 연습할 겸 사용해 보았다.

 

---