문제

To solve the swapping puzzle, use only two types of moves. Move one stone into the empty hole or jump one stone over one stone of the opposite color (into the empty hole)

You may not back up, and you may not jump over two stones.

/*Visual Studio 2015*/
/*C++*/

#include<iostream>  
#pragma warning(disable:4996) //scanf warning 해제
using namespace std;
#define MAX 180
int n = 3, idx;
int res[MAX];//움직인 돌의 위치를 저장할 배열
char state[MAX];//현재 돌의 배열상태를 나타낼 배열
void init()//초기화
{
	idx = 1;//몇번 움직였는지 카운트 할 인덱스
	for (int i = 1; i <= n; i++)//1~n번째 돌은 흰색
		state[i] = 'W';
	state[n + 1] = ' ';//n+1번째는 빈칸
	for (int i = n + 2; i <= 2 * n + 1; i++)//n+2번째 부터 2n+1까지 검은돌
		state[i] = 'B';
}
void swap(int &x, int &y)//돌의 위치를 바꾸는 함수
{
	int t;
	t = x;
	x = y;
	y = t;
}

void sum_show()//움직인 돌의 위치를 보여주는 함수
{//총 20개가 넘으면 개행하도록 함
	int sum = 0;
	for (int i = 1; i <= n*(n + 2); i++)
	{
		if (sum % 20 == 0)
			printf("%d", res[i]);
		else printf(" %d", res[i]);
		sum++;
		if (sum % 20 == 0)
			printf("\n");
	}
	if (sum % 20)
		printf("\n");
}

void puzzle(int hole, int cnt)//hole은 빈칸의 위치, cnt는 움직인 횟수
{
	if (cnt == idx)
		idx++;
	if (hole - 2>0 && state[hole - 2] == 'W' && state[hole - 1] == 'B')
	{//빈칸의 왼쪽에 2개 이상의 돌이 있고, 빈칸에서 왼쪽으로 2칸은 W, 1칸은 B일때
		swap(state[hole - 2], state[hole]);//빈칸 왼쪽에서 두번째 자리에 위치한 돌을 빈칸으로 점프
		res[cnt] = hole - 2;//움직인 돌은 빈칸에서 왼쪽으로 두번째 있는 돌이므로, res에 해당 위치를 저장
		if (cnt == n*(n + 2) && hole - 2 == n + 1)//답이라면(cnt가 2^n+2n이고, 빈칸의 위치가 가운데일경우
		{
			sum_show();//결과를 보여주고
			return;//리턴
		}
		else if (cnt<n*(n + 2))//답보다 작다면
			puzzle(hole - 2, cnt + 1);//현재 빈칸의 위치는 원래 빈칸에서 왼쪽으로 두칸 이동하였다.
									//돌이 움직인 횟수가 1 증가인 상태로 재귀호출
		swap(state[hole - 2], state[hole]);
	}
	if (hole - 1>0 && state[hole - 1] == 'W')//빈칸의 왼쪽에 1개 이상의 돌이 있고, 바로 왼쪽의 돌은 W일때
	{
		swap(state[hole - 1], state[hole]);//왼쪽에 있는 돌을 빈칸으로 옮긴다.
		res[cnt] = hole - 1;//움직인 돌은 빈칸 왼쪽에 있던 돌이였으므로, res에 추가한다.
		if (cnt == n*(n + 2) && hole - 1 == n + 1)//답이라면 답을 보여주고 리턴
		{
			sum_show();
			return;
		}
		else if (cnt<n*(n + 2))//답보다 작다면
			puzzle(hole - 1, cnt + 1);//빈칸의 위치는 하나 밀렸고 이동횟수는 1 증가
		swap(state[hole - 1], state[hole]);
	}
	if (hole + 1 <= 2 * n + 1 && state[hole + 1] == 'B')
	{
		swap(state[hole + 1], state[hole]);
		res[cnt] = hole + 1;
		if (cnt == n*(n + 2) && hole + 1 == n + 1)
		{
			sum_show();
			return;
		}
		if (cnt<n*(n + 2))
			puzzle(hole + 1, cnt + 1);
		swap(state[hole + 1], state[hole]);
	}
	if (hole + 2 <= 2 * n + 1 && state[hole + 2] == 'B' && state[hole + 1] == 'W')
	{
		swap(state[hole + 2], state[hole]);
		res[cnt] = hole + 2;
		if (cnt == n*(n + 2) && hole + 2 == n + 1)
		{
			sum_show();
			return;
		}
		if (cnt<n*(n + 2))
			puzzle(hole + 2, cnt + 1);
		swap(state[hole + 2], state[hole]);
	}
}
void main()
{
	while (n != 0)//0을 입력받을때까지 루프를 돌림
	{
		printf("input n = ");
		scanf("%d", &n);//n을 입력받음
		init();
		puzzle(n + 1, 1);//인덱스를 1부터 시작하기 위해 n+1을 대입
		printf("result : %d\n\n", idx - 1);//1부터 시작하였기에 -1을 하여 올바른 결과가 나오도록 함
	}
}

문제 : 정수로 이루어진 N x N 행렬이 있을때 사각형을 만들어 최대와 최소인 사각형을 만드는 알고리즘

출력 : 사각형의 좌측상단의 좌표, 우측하단의 좌표, 최댓값, 최솟값

/*Compiler : Visual Studio 2015 */
/*Language : C*/

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

#pragma warning(disable:4996)//scanf 경고 해제
#define MAX 1000

double calc(double* arr, int* first, int* last, int arr_size);
void findroot(double *arr[], int SizeOfArray);

int main()
{
	int SizeOfArray;
	double **arr;
	scanf("%d\n", &SizeOfArray);//행과 열의 크기를 먼저 받음
	arr = (double**)malloc(sizeof(double *)*SizeOfArray);
	for (int i = 0; i < SizeOfArray; i++)
	{
		arr[i] = (double *)malloc(sizeof(double)*SizeOfArray);
	}//동적배열 생성

	for (int i = 0; i < SizeOfArray; i++)
	{
		for (int j = 0; j < SizeOfArray; j++)
		{
			scanf("%lf", &arr[i][j]);
		}
	}//동적으로 받은 array에 데이터를 대입

	findroot(arr, SizeOfArray);
	//대입이 끝난 arr을 findroot에 배열의 행과 열의 크기와 함께 대입
	
	for (int i = 0; i<SizeOfArray; i++) 
	{
		free(arr[i]);
	}

	free(arr);	//array 동적할당 해제
	getchar();	//실행 후 종료됨 방지
	return 0;
}


void findroot(double *arr[], int SizeOfArray)
{
	int R_Left, R_Right, R_Up, R_Down, left, right, i, first, last;
	const int size = SizeOfArray;
	double maxSum = LONG_MIN, minSum = LONG_MIN, PartSum[MAX], sum;
	printf("\n%d x %d MATRIX\n", SizeOfArray, SizeOfArray);//행렬 정보 출력

	//Finding Maxvalue
	for (left = 0; left < SizeOfArray; ++left)
	{
		memset(PartSum, 0, sizeof(PartSum));
		for (right = left; right < SizeOfArray; ++right)
		{
			//left부터 right까지의 부분합을 구함
			for (i = 0; i < SizeOfArray; ++i)
			{
				PartSum[i] = PartSum[i] + arr[i][right];
			}
			sum = calc(PartSum, &first, &last, SizeOfArray);
			//1차원에서의 최소를 구함
			if (sum > maxSum)
			{
				maxSum = sum;
				R_Left = left;
				R_Right = right;
				R_Up = first;
				R_Down = last;
			}
		}
	}

	printf("\n(%d, %d) (%d, %d)\n", R_Up + 1, R_Left + 1, R_Down + 1, R_Right + 1);
	//첫번째 요소를 1,1로 잡기 위해 1씩 더해서 출력해줌
	printf("MaxSum is: %lf\n", maxSum);
	//printing maxvalue

	//Findidng minvalue
	for (int i = 0; i < SizeOfArray; i++)
	{
		for (int k = 0; k < SizeOfArray; k++)
		{
			arr[i][k] = (-1)*arr[i][k];//음수는 양수로 양수는 음수로 바꿔준다.
		}
	}

	//위의 maxvalue를 찾는것과 같은 코드
	for (left = 0; left < SizeOfArray; ++left)
	{
		memset(PartSum, 0, sizeof(PartSum));
		for (right = left; right < SizeOfArray; ++right)
		{
			//left부터 right까지의 부분합을 구한다.
			for (i = 0; i < SizeOfArray; ++i)
			{
				PartSum[i] += arr[i][right];
			}
			sum = calc(PartSum, &first, &last, SizeOfArray);
			//1차원에서의 최대를 구한다.
			if (sum > minSum)
			{
				minSum = sum;
				R_Left = left;
				R_Right = right;
				R_Up = first;
				R_Down = last;
			}
		}
	}
	minSum = (-1)*minSum; // 양, 음수를 바꿔계산한 결과를 다시 바꿔준다.
	printf("\n(%d, %d) (%d, %d)\n", R_Up + 1, R_Left + 1, R_Down + 1, R_Right + 1);
	printf("MinSum is: %lf\n", minSum);
	//printing minvalue
}

//1차원에서의 maxvalue를 구한다.
double calc(double* arr, int* first, int* last, int arr_size)
{
	double sum = 0, maxSum = LONG_MIN;
	int start_index=0, p=0;
	*last = -1; // 음수일 경우를 검사한다.

	for (int i = 0; i < arr_size; ++i)
	{
		sum += arr[i];
		if (sum < 0)
		{
			sum = 0;
			start_index = i + 1;
		}
		else if (sum > maxSum)
		{
			maxSum = sum;
			*first = start_index;
			*last = i;
		}
	}
	//음수를 검사한다.
	if (*last != -1)
		return maxSum;
	
	//모두 음수일때
	maxSum = arr[0];
	*first = 0;
	*last = 0;

	//가장 큰 원소를 찾는다. 
	for (int i = 1; i < arr_size; i++)
	{
		if (arr[i] > maxSum)
		{
			maxSum = arr[i];
			*first = i;
			*last = i;
		}
	}
	//test 모두 양수일때 minvalue test
	for(int i = 0; i < arr_size; i++)
	{
		for (int j = 0; j < arr_size; j++)
		{
			if (arr[i] >= 0)
				p = 1;
		}
	}
	if (p == 0)
		maxSum = arr[0];
	//test exit
	return maxSum;
}

자세한 설명은 주석을 참조하면 될것같다..

질문은 댓글주세요!